Problems

5. POWER

A new processor has been developed which for all practical purposes can store as large an integer as required and also totally eliminate errors occuring as a result of using floating point numbers.

So, what is the problem then? Well, the version available in the market so far is primitive in many other aspects due to difficulties out of scope of our discussion. The processor can use only two variables, a float variable c and an integer variable b. There are exactly three buttons which do the following functions on the two variables b and c.

1) Square - This function squares the variable b.
2) Multipliy- This function multiplies c,b and stores the result in c.
3) Divide - This function divides c by b and stores the result in c.

The square function is easy to implement so its usage does not involve any cost. However multiply and divide functions consume unit cost each every time they are used.

This processor is solely to be used for calculating a^e and storing the final result in c. You may note that at the beginning c automatically gets the value 1.0 and b can have any one of the following values: 0,1,a.

Naturally, you would like to reduce the costs. Fortunately, you always have a computer and a programming brain to pre-determine the minimum cost involved. Your task is to help decide the sequence of buttons pressed in the processor so that the total cost is minimised.

Input Format
There will be t<=100000 test cases in all.
First line contains the number of test cases
For every test case,there will be one line denoting a and e separated by a space

Output Format
A single integer on a new line, for every test case, denoting the minimum cost involved in this computation.

Constraints
2<=a<=2^31-1
1<=e<=10^18

Sample Input
2
12 31
15 17

Sample Output
2
2

Time Limit : 1s
Memory Limit: 64 MB