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