High School Programming League Problems Archive

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

a_n+2=2a_n+1-a_n+2

Each sequence of his concern starts with number a₁=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 a₂ is and no matter which n he chooses, one always can find an element of the sequence which equals a_na_n+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 a₂, n (2 ≤ a₂ ≤ 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 a_m=a_na_n+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.