Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 2964
Triangle

Time Limit: 2 Seconds      Memory Limit: 65536 KB

Find the minimum perimeter of any triangle if it is know that for the given non-negative integer a, z, its edge l, m, n (l > m > n and are all integers) satisfy {(a ^ l) / z} = {(a ^ m) / z} = {(a ^ n) / z}, in which {x} = x �C [x], ([x] is the maximum integer which is no more than x).

Input

The input contains multiple cases.

There is only one integer on the line 1, indicating the number of cases.

In each test case, there are 2 integer a, z (0 < a, z < 2 ^ 31, GCD(a, z) = 1)

Output

For each case, print the minimum perimeter of the triangle in a single line.

Sample Input

1
3 10000

Sample Output

3003

Author: ZHANG, Rui
Source: ZOJ Monthly, May 2008
Submit    Status