To tell the whole truth, creating a great number of programming problems is a huge project, Little Gyro was quite manic because of it, with the time flying quickly till midnight.
In order to calm down and keep the efficiency, Little Gyro bought some magical instant noodles for himself to eat at that time. Before eating the noodles, Little Gyro decided to pinch these noodles to pieces and enjoyed the pleasure of the sound.
Because of the magical composition of these noodles, In each step, Little Gyro can only take one piece of instant noodles, which would be divided into k pieces consisting of , if satisfies the equation . Otherwise, Little Gyro can't split it into pieces anymore. In addition, the number of pieces k can be an arbitrary number, but should be no less than 2 naturally.
Given a big piece of magical instant noodles of N-size, for each step, Little Gyro would make it into pieces as small as he can, until he can't take it apart anymore, because he was very mad and crazy. Now you are asked to tell the maximum number of times he can pinch for.

There are multiple test cases. The first line of the input contains an integer T (1 ≤ T ≤ 1000), indicating the number of test cases. For each test case:
Each line contains a single integer N (0 ≤ N ≤ ), indicating the size of the magical instant noodles.

For each test case, output the maximum operation step of splitting the magical instant noodles.

3
1
3
10

0
1
2