同和创作矩阵 › ›博文归档› 技术博文归档 › 查看内容

21817_Fibonacci

2022-5-16 18:20| 发布者: Hocassian| 查看: 23| 评论: 0|原作者: 肇庆学院ACM合集

摘要:

C:\Users\Administrator\Downloads\2019-10-12-10-14-4-89505874346400-Problem List-采集的数据-后羿采集器.html

Pro.ID

21817

Title

Fibonacci

Title链接

http://10.20.2.8/oj/exercise/problem?problem_id=21817

AC

Submit

Ratio

50.00%

时间&空间限制

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65535 K (Java/Others)

描述

We know the Fibonacci Sequence

F₁=1, F₂=1, F₃=2, F₄=3, F₅=5,
...
F_x = F_x-1+ F_x-2

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

For example,

F₁₅ = 610

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

F₃₀₀ = 222232244629420445529739893461909967206666939096499764990979600.

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

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

输入

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.

输出

Description

We know the Fibonacci Sequence

F₁=1, F₂=1, F₃=2, F₄=3, F₅=5,
...
F_x = F_x-1+ F_x-2

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

For example,

F₁₅ = 610

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

F₃₀₀ = 222232244629420445529739893461909967206666939096499764990979600.

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

Of course, the F_x may be very large if M and K are big. So we only want to know the subscript of F_x (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 M-th number which has K consecutive 0s at the end of F_x. ( You can believe the answer is smaller than 2³¹ )

Sample Input

3
1 1
2 2
2 5

Sample Output

15
300
900

Source

2009 Multi-University Training 15

样例输入