Fibonacci

Time Limit: 1000ms
Memory Limit: 65535KB
This problem will be judged on HDU. Original ID: 3054
64-bit integer IO format: %I64d      Java class name: Main

Description

We know the Fibonacci Sequence

F1=1,F2=1,F3=2,F4=3,F5=5,

...

Fx = Fx-1+Fx-2

We want to know the Mth number which has K consecutive "0" at the end of Fx.

For example,

F15=610

It is the first number which has only one "0" at the end.

F300=222232244629420445529739893461909967206666939096499764990979600.

It is the second number which has two "0" at the end.

Of course, the Fx may be very large if M and K are big. So we only want to know the subscript of Fx (it means the "x" For a given M and K)

Input

Input includes multiple cases.

First line is the number of case x

The next x lines: Each line contains two integer number, K and M, divided by a space.

Output

For each case:

Print a integer number in a line, is the Mth number which has K consecutive 0s at the end of Fx. (You can believe the answer is smaller than 2^31);

Sample Input

3
1 1
2 2
2 5

Sample Output

15
300
900

Source

Language: 
Theme: 
Share Code? 

Powered by NB231 | Current Style: .