HE: Rasta and Darie

A Darie is a special circle. Numbers 1, 2, ..., n are written clockwise around this circle in order. You can stand on a number! Initially Rasta is on number 1. In each step, he jumps exactly p numbers clockwise. For example if n = 3 and he is standing on number 1:

If p = 1 then he jumps to number 2.

Or if p = 2 he jumps to number 3.

He does this until he reaches a number he's been on before (for example, if n = 3, p = 1 he stops after three jumps).

Then he writes down the numbers he had been on, as a sequence s in increasing order.

He's not a Mr.Memmory, so he can't remember this sequence. He asks you to help him by telling him the k-th number in this sequence (or -1 if size of s is less than k).

Input format

The first line of input contains an integer t, the number of testcases (1 ≤ t ≤ 10⁵).

Each testcase is given in one line, which contains three integers n, p, k (2 ≤ n ≤ 10⁶, 1 ≤ p ≤ n - 1, 1 ≤ k ≤ 10⁶).

Output format

Print the answer of each testcase in one line.

---

Sample Input

(Plaintext Link)

3
12 5 3
12 3 2
3 2 2

Sample Output

(Plaintext Link)

3
4
2

PROGRAM-

#include <stdio.h>
#include<math.h>

int b[20];
int main()
{

 int tc,n,p,k,i,j,d,m,tmp,s,pos,x,br;
 int flag=0;
 
 int input[100][100];

   scanf("%d",&tc);
   for(i=0;i<tc;i++)
   for(j=0;j<3;j++)
   scanf("%d",&input[i][j]);
   
   for(i=0;i<tc;i++)
   {
    flag=0;
    n=input[i][0];
    p=input[i][1];
    k=input[i][2];
    d=1;
    m=0;
    while(flag==0){
if(d==0) b[m]=n;
else b[m]=d;

     d=(d+p)%n;

m++;
     for(br=0; br<m; br++)
     if(b[br]==d){ flag=1; }
     
    }
    
for(x=0;x<m;x++)
{
 pos=x;
 for(s=x+1;s<m;s++){
if(b[pos]>b[s]) pos=s;}
tmp=b[pos];
b[pos]=b[x];
b[x]=tmp;
}



   printf("%d \n",b[k-1]);
   
      
   }

}