Harsh just loves numbers and loves to have fun with them . Apparently he has two numbers with him , say X and Y . Both of them are integers . Now from these numbers he wants another number , say L . But he doesn’t know how to derive it and needs your help . Given the two numbers you can add one to another , and you can do this any number of times . For example, you can add X to Y , or Y to X , and this can be done until any combination makes either X equal to L or Y equal to L .

“Well , this might actually lead to a solution”, said Harsh, ”but can you do it in a minimum number of operations ?”.

Just to make this problem a little simple let’s assume both the values of X and Y is 1 .

Input Format:

The first line contains T, the number of test cases. For each test case, the first line contains L ,the value that Harsh wants .

Output Format:

For each test case, output the required minimum number of operations .

Constraints:
1 ≤ T ≤20
1 ≤ L ≤1000000

SAMPLE INPUT
1
3

SAMPLE OUTPUT
2

Explanation

Add X to Y , and then add Y to X . Value of X is 3 and value of Y is 2 .

The minimum number of steps is 2 .

见题面

见题面