Problem hidden
This problem was hidden by Editorial Board member probably because it has incorrect language version or invalid test data, or description of the problem is not clear.

HS09REC - Recursive sequences

Bernie wishes to impress his math teacher with a new theorem. He observes some sequences which satisfy a recursive relation

an+2=2an+1-an+2

Each sequence of his concern starts with number a1=1, but the second numbers differ. Bernie thinks he found a nice rule, which he wants to check. He thinks that no matter what the number a2 is and no matter which n he chooses, one always can find an element of the sequence which equals anan+1.

You can help him in his investigations by finding required elements.

Input

There is K (1 ≤ K ≤ 1 000) lines of standard input. Each consists of two integer numbers a2, n (2 ≤ a2 ≤ 1 000, 1 ≤ n ≤ 1 000 000 000) separated by spaces.

The line K+1 will contain two zeros, which shouldn't be processed.

Output

Write out K lines of output - one for each testcase. For each testcase the line should contain the smallest positive integer m such that am=anan+1 or the number 0 if such an m doesn't exist.

Example

Input:
2 1 2 2 2 4 3 5 0 0 Output: 2 4 14 26

Scoring

For solving this problem you will score 10 points.


Added by:Adam Dzedzej
Date:2010-01-30
Time limit:0.200s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: CLOJURE NODEJS OBJC PERL6 SQLITE VB.NET
Resource:High School Programming League (thanks to Talent Association)

hide comments
2012-06-15 17:04:41 kuszi
@cegprakash there is no a0 as n>=1
2010-07-23 19:57:01 cegprakash
pls make the problem statement clear

a[n]=2a[n-1] - a[n-2] +2

and

a[m]= a[n]*a[n+1]

what i'm expected to find

for the test case 3 5 how the output will be 26. can u pls xplain?
2010-07-23 19:42:15 cegprakash
what is a0???
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.