#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; }

#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;
}