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