T4

有N个方块排成一列，编号从0--（n-1），有以下步骤标记方块

1. 令$x= (A+D)$%$N$ A为上次标记的地方
2. 若x已经被标记，替换$x=(x+1)$%$N$
3. 标记x

题目要求：输出第$K$次标记的方块的编号

$我们不妨将N分为g=gcd(N,D)段，那么第K次标记的编号为第i段第j个$

#include<bits/stdc++.h>
using namespace std;
long long t,k,n,d;
long long gcd(long long a,long long b){
	if(b==0) return a;
	return gcd(b,a%b);
}
int main(){
	freopen("D.in","r",stdin);
	freopen("D.out","w",stdout);
    cin>>t;
    while(t--){
    	cin>>n>>d>>k;
    	if(k==1){
    		cout<<0<<endl;
    		continue;
		}
        k--;
    	cout<<(k*d+k/(n/gcd(n,d)))%n<<endl;
	}
	return 0;
}