G :: Circular Board Game

Time Limit: 3 Seconds    Memory Limit: 32768 KB

In the city of Bigwood there is a popular board game named Expo in which the board has a circular shape with N cells (1 to N). This game, same as many other board games, is played using tokens and a die. Players take turn to roll a K-sided die but the movement based on the number rolled is not that simple. The rule is that, assuming the side S has appeared, you move your token expo(S) cells forward. Where expo(S) = S^{(S-1)(S-2)...(2)(1)} . As the board is circular, the movement will continue when we reach to the last cell. The goal is to put your token in the last cell starting from the first one. (Ofcourse not in the middle of a movement)
Brad and Pete are playing this game. But as you may have noticed, for larger amounts of S, it might take a lifetime (or even much much more!) to move the token from one cell to the next one for expo(S) times. Actually, their grandfathers couldn’t finish the game they had started when they were young in the traditional way. So Brad and Pete are playing on behalf of their grandfathers and expect you to help.
Find the destination cell for a given side S on the die, starting from Mth cell. 

Input

The first line of input contains one integer T (1 ≤ T ≤ 256), which is the number of test cases.
For each test case: three space separated integers S (1 ≤ S ≤ 10⁹), M, and N (1 ≤ M ≤ N ≤ 10⁹). 

 

Output

For each test, print a single line containing the place token lies on the board after the movement.

Sample Input

3
2 1 39
94 250 265
5 123 123456789

Sample Output

3
24
16317757

Submit

Source: 14th Iran Nationwide Internet Contest