Time Limit: 1.0 s

Memory Limit: 256.0 MB

Description

Roy and Hridoy are playing a game called SeriousOJ. The game starts with two positive integers, n and m, and a fixed number of moves k.
In each move:

• Roy's Turn:

  • Roy chooses an integer \(x\) from the range \([1, m]\).
  • Then He updates \(n\) to either \(n + x\) or \(n-x\). (Note : He can subtract \(x\) from the \(n\), only when \(n-x >= 2\), otherwise he must update \(n\) to \(n+x\)).

• Hridoy's Turn:

  • Hridoy finds the largest divisor \(d\) of \(n\) such that \(1 <= d < n\).
  • Then He updates \(n\) to \(n / d\).

Roy wants to maximize the final value of n, where Hridoy wants to minimize it.
Note : In each move Roy goes first.

Input

First line T, the number of test case.
In each test case, input contains three positive integers: n, m, and k.

\(1<=T<=10\)
\(2<=n<= 3* 10^5\)
\(1<=m<=100\)
\(1<=k<=10^9\)

Output

In each test case, print a single integer: the final value of n after k moves, assuming both players play optimally.

Sample

2

2 2 2

2 1 2

5

2

First test case :
initially \(n=2\),
1st move :

• Roy pick \(x=1\), from 1 to m and add it into n. Now, \(n=n+x=2+1=3\).
• Hridoy finds the largest divisor of \(n=3\) is \(d=1\), and divide it. Now, \(n = n/d= 3/1 = 3\).

2nd move :

• Roy pick \(x=2\), from 1 to m and add it into n. Now, \(n=n+x=3+2=5\).
• Hridoy finds the largest divisor of \(n=5\) is \(d=1\), and divide it. Now, \(n = n/d= 5/1 = 5\).

After k moves final value of n is 5, which is maximum.