C++ :

#include<bits/stdc++.h>
using namespace std;
long long m;
int g,n,t,a[300005];
int main()
{
	cin>>g;
	while(g--)
	{
		cin>>n>>m>>t;
		fill(a,a+300004,0);
		int ans=0;
		for(long long i=0;i<n;i++)
			a[i]=1+(i*i)%m;
//		for(int i=0;i<n;i++)
//			cout<<a[i]<<" ";
		sort(a,a+n);
		for(int i=0;i<n;i++)
		{
			int j=i;
			while(a[j]==a[j+1]) j++;
			int tmp=j-i+1+min(t,n-j-1);
			ans=max(ans,tmp);
			i=j;
		}
		cout<<ans<<endl;
	}
    return 0;
}