#include<bits/stdc++.h> using namespace std; int a[300010]; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t; cin>>t; while(t--) { int n,m,k,s=1,maxn=-1; cin>>n>>m>>k; if(m==1) { cout<<n<<'\n'; continue; } for(int i=1;i<=n;i++) { long long j=i-1; a[i]=(j*j%m)+1; } sort(a+1,a+n+1); a[n+1]=-1; for(int i=2;i<=n+1;i++) if(a[i]==a[i-1])s++; else { maxn=max(maxn,s+min(k,n-i+1)); s=1; } cout<<maxn<<'\n'; } return 0; }