#include #include #include using namespace atcoder; using mint = modint998244353; using namespace std; #define rep(i,n) for (int i = 0; i < (n); ++i) #define Inf32 1000000001 #define Inf64 1000000000000000001 int main(){ int _t; cin>>_t; rep(_,_t){ int K,M,N; cin>>K>>M>>N; M--; vector f(K); vector ans; rep(i,K){ if(f[i])continue; int c = i; while(true){ int x = c,y = ((c+M)%K); if(f[x]||f[y])break; if(x==y)break; ans.push_back(c); f[x] = 1; f[y] = 1; c += M*2; c %= K; } } if(ans.size()