stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#include <cstdio>

#include <vector>

#include <algorithm>

using namespace std;



int main(){

	int h, n, p, m, k;

	scanf("%d%d%d%d%d", &h, &n, &p, &m, &k);

	vector<int> v(h, -1);

	for(int i = 0; i < m; ++i){

		int a, b;

		scanf("%d%d", &a, &b);

		v[a - 1] = b - 1;

	}



	double cmb[512][512] = {};

	for(int i = 0; i < 512; ++i){

		cmb[i][0] = 1;

		for(int j = 1; j <= i; ++j){

			cmb[i][j] = cmb[i - 1][j - 1] + cmb[i - 1][j];

		}

	}



	int rst = h - m;

	vector<vector<double> > dp1(k + 1, vector<double>(n)), dp2;

	dp2 = dp1;

	dp1[k][p - 1] = 1;

	for(int g = h - 1; g >= 0; --g){

		if(v[g] == -1){

			dp2[0] = dp1[0];

			for(int i = 1; i <= k; ++i){

				double pr1 = 1 - cmb[rst - 1][i] / cmb[rst][i];

				double pr2 = pr1 / (n - 1);

				for(int j = 0; j < n; ++j){

					dp2[i][j] = dp1[i][j] * (1 - pr1);

				}

				dp2[i - 1][0] += (dp1[i][0] * (n - 2) + dp1[i][1]) * pr2;

				dp2[i - 1][n - 1] += (dp1[i][n - 1] * (n - 2) + dp1[i][n - 2]) * pr2;

				for(int j = 1; j < n - 1; ++j){

					dp2[i - 1][j] += (dp1[i][j] * (n - 3) + dp1[i][j - 1] + dp1[i][j + 1]) * pr2;

				}

			}

			dp1.swap(dp2);

			--rst;

		}

		else{

			for(int i = 0; i <= k; ++i){

				swap(dp1[i][v[g]], dp1[i][v[g] + 1]);

			}

		}

	}

	double ans = *max_element(dp1[0].begin(), dp1[0].end());

	printf("%.9f\n", ans);

}

// Faster C++ solution for the same problem (measured speedup: 3.5473784102988093x):
#include <cstdio>

#include <vector>

#include <algorithm>

using namespace std;



int main(){

	int h, n, p, m, k;

	scanf("%d%d%d%d%d", &h, &n, &p, &m, &k);

	vector<int> v(h, -1);

	for(int i = 0; i < m; ++i){

		int a, b;

		scanf("%d%d", &a, &b);

		v[a - 1] = b - 1;

	}



	int rst = h - m;

	vector<vector<double> > dp1(k + 1, vector<double>(n)), dp2;

	dp2 = dp1;

	dp1[k][p - 1] = 1;

	for(int g = h - 1; g >= 0; --g){

		if(v[g] == -1){

			dp2[0] = dp1[0];

			for(int i = 1; i <= k; ++i){

				double pr1 = (double)i / rst;

				double pr2 = pr1 / (n - 1);

				for(int j = 0; j < n; ++j){

					dp2[i][j] = dp1[i][j] * (1 - pr1);

				}

				dp2[i - 1][0] += (dp1[i][0] * (n - 2) + dp1[i][1]) * pr2;

				dp2[i - 1][n - 1] += (dp1[i][n - 1] * (n - 2) + dp1[i][n - 2]) * pr2;

				for(int j = 1; j < n - 1; ++j){

					dp2[i - 1][j] += (dp1[i][j] * (n - 3) + dp1[i][j - 1] + dp1[i][j + 1]) * pr2;

				}

			}

			dp1.swap(dp2);

			--rst;

		}

		else{

			for(int i = 0; i <= k; ++i){

				swap(dp1[i][v[g]], dp1[i][v[g] + 1]);

			}

		}

	}

	double ans = *max_element(dp1[0].begin(), dp1[0].end());

	printf("%.9f\n", ans);

}
// Slower C++ solution:
#include<iostream>

#include<cstring>

#include<cstdlib>

using namespace std;

int maps[1005][1005];

int main() {

	int h,w,a,b;

	cin>>h>>w>>a>>b;

	memset(maps,0,sizeof(maps));

	for(int i=1; i<=b; i++) {

		for(int j=a+1; j<=w; j++) {

			maps[i][j]=1;

		}

	}

	for(int i=b+1; i<=h; i++) {

		for(int j=1; j<=a; j++) {

			maps[i][j]=1;

		}

	}

	for(int i=1; i<=h; i++) {

		for(int j=1; j<=w; j++)cout<<maps[i][j];

		cout<<'\n';

	}

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.030314650932642x):
#include<iostream>



using namespace std;



int main(){

    int H, W, A, B;

    cin >> H >> W >> A >> B;

    for(int i=1; i<=H; i++){

        for(int j=1; j<=W; j++){

            if((i<=B && j<=A) || (i>B && j>A)){

                cout << 0;

            } else{

                cout << 1;

            }

        }

        cout << endl;

    }

    

}
// Slower C++ solution:
#include<iostream>

#include<cstring>

#include<cstdlib>

using namespace std;

int maps[1005][1005];

int main() {

	int h,w,a,b;

	cin>>h>>w>>a>>b;

	memset(maps,0,sizeof(maps));

	for(int i=1; i<=b; i++) {

		for(int j=a+1; j<=w; j++) {

			maps[i][j]=1;

		}

	}

	for(int i=b+1; i<=h; i++) {

		for(int j=1; j<=a; j++) {

			maps[i][j]=1;

		}

	}

	for(int i=1; i<=h; i++) {

		for(int j=1; j<=w; j++)cout<<maps[i][j];

		cout<<'\n';

	}

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 4.98683399649362x):
#include <bits/stdc++.h>



using namespace std;



#define ull unsigned long long

#define ll long long

#define ui unsigned int

#define us unsigned short

#define inf_int 1e9

#define inf_ll 1e18



int main(){

	ios_base::sync_with_stdio(0);

    cin.tie(0);

    cout.tie(0);

	

	int h, w, a, b;

	cin >> h >> w >> a >> b;

		

	for(us x=0;x<h;x++){

		for(us y=0;y<w;y++){

			if((x < b && y >= a) || (x >= b && y < a)) cout << 1;

			else cout << 0;

		}

		cout << "\n";

	}



    return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

#define maxn 800

#define maxm 1009

using namespace std;

int b[maxn][maxn],a[maxn][maxn];

int  guass(int n)

{

	int i,j,p,row=0,col=0;

	for(;row<n&&col<n;row++,col++)

	{

		for(i=row,p=row;i<n;i++)

			if(a[i][col])

			{p=i;break;}

		if(p!=row)

			for(j=col;j<=n;j++)

				swap(a[p][j],a[row][j]);

		if(!a[row][col]) 

		{

			row--;

			continue;

		}

		for(i=row+1;i<n;i++)

			if(a[i][col])

			for(j=col+1;j<=n;j++)

				a[i][j]^=a[row][j];

	}

	for(i=row;i<n;i++)

		if(a[i][n]) return 0;

	return 1;

}

int main()

{

	int n,m,d;

	while(scanf("%d%d%d",&m,&n,&d)!=EOF&&n+m+d)

	{

		for(int i=0;i<n;i++)

		{

			for(int j=0;j<m;j++)

				scanf("%d",&b[i][j]);

		}

		memset(a,0,sizeof(a));

		for(int i=0;i<n;i++)

		{

			for(int j=0;j<m;j++)

			{

				a[i*m+j][n*m]=b[i][j];

				a[i*m+j][i*m+j]=1;

				for(int x=0;x<n;x++)

				{

					for(int y=0;y<m;y++)

					{

						if(abs(x-i)+abs(y-j)==d)

							a[i*m+j][x*m+y]=1;

					}

				}

			}

		}

		if(guass(n*m))

			puts("1");

		else

			puts("0");

	}

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 8.354812910269017x):
#include <cstdio>

#include <cstring>

#include <bitset>

#include <iostream>

#include <cmath>



using namespace std;



int n, m, D;

int a[30][30];

bitset <650> G[650];



inline int id(int x, int y) {

    return x * m + y;

}



bool Gauss(int equ, int var) {

    int col = 0, k;

    for(k = 0; k < equ && col < var; ++k, ++col) {

        if(!G[k][col]) {

            for(int i = k + 1; i < equ; ++i) if(G[i][col]) {

                G[k] ^= G[i];

                break;

            }

        }

        if(!G[k][col]) {

            k--;

            continue;

        }

        for(int i = k + 1; i < equ; ++i) 

			if(G[i][col]) 

				G[i] ^= G[k];

    }

    for(int i = k; i < equ; ++i) 

		if(G[i][var]) 

			return 0;

    return 1;

}



int main() {

    while(scanf("%d%d%d", &m, &n, &D)) {

        if(n == 0) break;

        for(int i = 0; i < n; ++i) 

			for(int j = 0; j < m; ++j) 

				scanf("%d", &a[i][j]);

        int U = n * m;

        for(int i = 0; i < U; ++i) G[i].reset();

        for(int i = 0; i < n; ++i) 

			for(int j = 0; j < m; ++j) {

	            int u = id(i, j);

	            G[u][u] = 1;

	            for(int x = 0; x < n; ++x) 

					for(int y = 0; y < m; ++y) {

		                if(abs(x - i) + abs(y - j) != D) continue;

		                G[id(x, y)][u] = 1;

		            }

        }

        for(int i = 0; i < n; ++i) 

			for(int j = 0; j < m; ++j) {

            if(!a[i][j]) continue;

            G[id(i, j)][n * m] = 1;

        }

        puts(Gauss(n * m, n * m) ? "1" : "0");

    }

    return 0;

}
// Slower C++ solution:
#include <cstdio>

#include <vector>

#include <bitset>

using namespace std;





inline bool in(int a, int b, int c){

	return a <= b && b < c;

}





int main(){

	int m, n, d, s;

	while( scanf("%d%d%d", &m, &n, &d), m != 0 ){

		int sz = m * n;

		vector<bitset<626> > v(sz);

		bitset<625> used;



		int p = 0;

		for(int i = 0; i < n; ++i){

			for(int j = 0; j < m; ++j, ++p){

				v[p][p] = true;

				

				for(int k = 0; k < d; ++k){

					if( in(0, i - d + k, n) && in(0, j + k, m) ){

						v[p][(i - d + k) * m + (j + k)] = true;

					}

					if( in(0, i + k, n) && in(0, j + d - k, m) ){

						v[p][(i + k) * m + (j + d - k)] = true;

					}

					if( in(0, i + d - k, n) && in(0, j - k, m) ){

						v[p][(i + d - k) * m + (j - k)] = true;

					}

					if( in(0, i - k, n) && in(0, j - d + k, m) ){

						v[p][(i - k) * m + (j - d + k)] = true;

					}

				}



				scanf("%d", &s);

				if( s != 0 ){

					v[p][sz] = true;

				}

			}

		}



		for(int i = 0; i < sz; ++i){

			int index = -1;



			for(int j = 0; j < sz; ++j){

				if( !used[j] && v[j][i] ){

					index = j;

					used[j] = true;

					break;

				}

			}



			if( index >= 0 ){

				for(int j = 0; j < sz; ++j){

					if( j == index || !v[j][i] ) continue;



					for(int k = 0; k <= sz; ++k){

						if( v[index][k] ){

							v[j].flip(k);

						}

					}

				}

			}

		}





		int ans = 1;

		for(int i = 0; i < sz; ++i){

			if( v[i][sz] && v[i].count() == 1 ){

				ans = 0;

				break;

			}

		}

		

		printf("%d\n", ans);

	}

}

// Faster C++ solution for the same problem (measured speedup: 2.8799547199817104x):
#include <cstdio>

#include <vector>

#include <bitset>

using namespace std;





inline bool in(int a, int b, int c){

	return a <= b && b < c;

}





int main(){

	int m, n, d, s;

	while( scanf("%d%d%d", &m, &n, &d), m != 0 ){

		int sz = m * n;

		vector<bitset<626> > v(sz);

		bitset<625> used;



		int p = 0;

		for(int i = 0; i < n; ++i){

			for(int j = 0; j < m; ++j, ++p){

				v[p][p] = true;

				

				for(int k = 0; k < d; ++k){

					if( in(0, i - d + k, n) && in(0, j + k, m) ){

						v[p][(i - d + k) * m + (j + k)] = true;

					}

					if( in(0, i + k, n) && in(0, j + d - k, m) ){

						v[p][(i + k) * m + (j + d - k)] = true;

					}

					if( in(0, i + d - k, n) && in(0, j - k, m) ){

						v[p][(i + d - k) * m + (j - k)] = true;

					}

					if( in(0, i - k, n) && in(0, j - d + k, m) ){

						v[p][(i - k) * m + (j - d + k)] = true;

					}

				}



				scanf("%d", &s);

				if( s != 0 ){

					v[p][sz] = true;

				}

			}

		}



		for(int i = 0; i < sz; ++i){

			int index = -1;



			for(int j = 0; j < sz; ++j){

				if( !used[j] && v[j][i] ){

					index = j;

					used[j] = true;

					break;

				}

			}



			if( index >= 0 ){

				for(int j = 0; j < sz; ++j){

					if( j != index && v[j][i] ){

						v[j] ^= v[index];

					}

				}

			}

		}





		int ans = 1;

		for(int i = 0; i < sz; ++i){

			if( v[i][sz] && v[i].count() == 1 ){

				ans = 0;

				break;

			}

		}

		

		printf("%d\n", ans);

	}

}
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;

typedef vector<int> vec;

typedef vector<vec> mat;

const double EPS=1E-9;

bool gauss_jordan(const mat& A,const vec& b){

  int n=A.size();

  mat B(n,vec(n+1));

  for(int i=0;i<n;i++)

    for(int j=0;j<n;j++)B[i][j]=A[i][j];

  

  for(int i=0;i<n;i++)B[i][n]=b[i];

  

  for(int i=0;i<n;i++){

    int pivot=i;

    for(int j=i;j<n;j++)if(abs(B[j][i])>abs(B[pivot][i]))pivot=j;

    swap(B[i],B[pivot]);



    for(int j=0;j<n;j++)

      if(i!=j)

	for(int k=i+1;k<=n;k++)B[j][k]=(B[j][k]+B[j][i]*B[i][k])%2;

  }

  vec x(n);

  for(int i=0;i<n;i++)x[i]=B[i][n];

  for(int i=0;i<n;i++)if(B[i][i]==0&&x[i]==1) return 0;

  return 1;

}



int h,w,d,mp[25][25];



int main(){

  while(1){

    cin>>w>>h>>d;

    if(!w&&!h&&!d)break;

    mat A(h*w,vec(h*w));

    vec B(h*w);

    for(int i=0;i<h;i++)

      for(int j=0;j<w;j++)cin>>mp[i][j];

    

    for(int i=0;i<h;i++)

      for(int j=0;j<w;j++){

	int idx=w*i+j;

	B[idx] = mp[i][j];

	for(int y=0;y<h;y++)

	  for(int x=0;x<w;x++){

	    int t = abs(i-y)+abs(j-x);

	    if(t==d||t==0)A[idx][w*y+x]=1;				

	  }

      }

    cout<<gauss_jordan(A,B)<<endl;

  }

  return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.8628295114262532x):
#include <bits/stdc++.h>

using namespace std;

typedef vector<int> vec;

typedef vector<vec> mat;

const double EPS=1E-9;

bool gauss_jordan(const mat& A,const vec& b){

  int n=A.size();

  mat B(n,vec(n+1));

  for(int i=0;i<n;i++)

    for(int j=0;j<n;j++)B[i][j]=A[i][j];

  

  for(int i=0;i<n;i++)B[i][n]=b[i];

  

  for(int i=0;i<n;i++){

    int pivot=i;

    for(int j=i;j<n;j++)if(abs(B[j][i])>abs(B[pivot][i]))pivot=j;

    swap(B[i],B[pivot]);

    for(int j=0;j<n;j++)

      if(i!=j&&B[j][i])

	for(int k=i;k<=n;k++)B[j][k]=(B[j][k]+B[i][k])%2;

  }

  for(int i=0;i<n;i++)if(B[i][i]==0&&B[i][n]==1) return 0;

  return 1;

}



int h,w,d,mp[25][25];



int main(){

  while(1){

    cin>>w>>h>>d;

    if(!w&&!h&&!d)break;

    mat A(h*w,vec(h*w));

    vec B(h*w);

    for(int i=0;i<h;i++)

      for(int j=0;j<w;j++)cin>>mp[i][j];

    

    for(int i=0;i<h;i++)

      for(int j=0;j<w;j++){

	int idx=w*i+j;

	B[idx] = mp[i][j];

	for(int y=0;y<h;y++)

	  for(int x=0;x<w;x++){

	    int t = abs(i-y)+abs(j-x);

	    if(t==d||t==0)A[idx][w*y+x]=1;				

	  }

      }

    cout<<gauss_jordan(A,B)<<endl;

  }

  return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;

typedef vector<int> vec;

typedef vector<vec> mat;

const double EPS=1E-9;

bool gauss_jordan(const mat& A,const vec& b){

  int n=A.size();

  mat B(n,vec(n+1));

  for(int i=0;i<n;i++)

    for(int j=0;j<n;j++)B[i][j]=A[i][j];

  

  for(int i=0;i<n;i++)B[i][n]=b[i];

  

  for(int i=0;i<n;i++){

    int pivot=i;

    for(int j=i;j<n;j++)if(abs(B[j][i])>abs(B[pivot][i]))pivot=j;

    swap(B[i],B[pivot]);



    for(int j=0;j<n;j++)

      if(i!=j)

	for(int k=i+1;k<=n;k++)B[j][k]=(B[j][k]+B[j][i]*B[i][k])%2;

  }

  for(int i=0;i<n;i++)if(B[i][i]==0&&B[i][n]==1) return 0;

  return 1;

}



int h,w,d,mp[25][25];



int main(){

  while(1){

    cin>>w>>h>>d;

    if(!w&&!h&&!d)break;

    mat A(h*w,vec(h*w));

    vec B(h*w);

    for(int i=0;i<h;i++)

      for(int j=0;j<w;j++)cin>>mp[i][j];

    

    for(int i=0;i<h;i++)

      for(int j=0;j<w;j++){

	int idx=w*i+j;

	B[idx] = mp[i][j];

	for(int y=0;y<h;y++)

	  for(int x=0;x<w;x++){

	    int t = abs(i-y)+abs(j-x);

	    if(t==d||t==0)A[idx][w*y+x]=1;				

	  }

      }

    cout<<gauss_jordan(A,B)<<endl;

  }

  return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.8396349221222628x):
#include <bits/stdc++.h>

using namespace std;

typedef vector<int> vec;

typedef vector<vec> mat;

const double EPS=1E-9;

bool gauss_jordan(const mat& A,const vec& b){

  int n=A.size();

  mat B(n,vec(n+1));

  for(int i=0;i<n;i++)

    for(int j=0;j<n;j++)B[i][j]=A[i][j];

  

  for(int i=0;i<n;i++)B[i][n]=b[i];

  

  for(int i=0;i<n;i++){

    int pivot=i;

    for(int j=i;j<n;j++)if(abs(B[j][i])>abs(B[pivot][i]))pivot=j;

    swap(B[i],B[pivot]);

    for(int j=0;j<n;j++)

      if(i!=j&&B[j][i])

	for(int k=i;k<=n;k++)B[j][k]=(B[j][k]+B[i][k])%2;

  }

  for(int i=0;i<n;i++)if(B[i][i]==0&&B[i][n]==1) return 0;

  return 1;

}



int h,w,d,mp[25][25];



int main(){

  while(1){

    cin>>w>>h>>d;

    if(!w&&!h&&!d)break;

    mat A(h*w,vec(h*w));

    vec B(h*w);

    for(int i=0;i<h;i++)

      for(int j=0;j<w;j++)cin>>mp[i][j];

    

    for(int i=0;i<h;i++)

      for(int j=0;j<w;j++){

	int idx=w*i+j;

	B[idx] = mp[i][j];

	for(int y=0;y<h;y++)

	  for(int x=0;x<w;x++){

	    int t = abs(i-y)+abs(j-x);

	    if(t==d||t==0)A[idx][w*y+x]=1;				

	  }

      }

    cout<<gauss_jordan(A,B)<<endl;

  }

  return 0;

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

using Int = long long;

//INSERT ABOVE HERE

int s[1010][1010];

signed main(){

  int n;

  cin>>n;

  memset(s,0,sizeof(s));

  for(int i=0;i<n;i++)

    for(int j=0;j<n;j++)

      if((i+j)%2==0) s[i][j]=1;

  for(int i=0;i<n;i+=3)

    for(int j=0;j<n;j++)

      s[i][j]=1;

  for(int j=0;j<n;j++)

    s[n-1][j]=1;

  for(int i=0;i<n;i++)

    s[i][0]=1;



  using P = pair<int, int>;

  vector<P> ans;

  for(int i=0;i<n;i++)

    for(int j=0;j<n;j++)

      if(((i+j)&1)&&s[i][j]) ans.emplace_back(i,j);



  cout<<ans.size()<<endl;

  for(auto p:ans) cout<<p.first<<" "<<p.second<<endl;

  return 0;

}


// Faster C++ solution for the same problem (measured speedup: 5.14253585697272x):
#include<bits/stdc++.h>

using namespace std;

using Int = long long;

template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}

template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}





template<typename V>

V compress(V v){

  sort(v.begin(),v.end());

  v.erase(unique(v.begin(),v.end()),v.end());

  return v;

}

template<typename T>

map<T, Int> dict(const vector<T> &v){

  map<T, Int> res;

  for(Int i=0;i<(Int)v.size();i++)

    res[v[i]]=i;

  return res;

}

map<char, Int> dict(const string &v){

  return dict(vector<char>(v.begin(),v.end()));

}



//INSERT ABOVE HERE

signed main(){

  Int n;

  cin>>n;



  using P = pair<Int, Int>;

  vector<P> ans;



  Int d=n%3;

  for(Int i=0;i<n;i++){

    for(Int j=0;j<n;j++){

      if((i+j)%2==0) continue;

      if(i==0||j==0) ans.emplace_back(i,j);



      if(i<d) continue;

      if((i-d)%3==1) ans.emplace_back(i,j);

    }

  }





  ans=compress(ans);

  cout<<ans.size()<<endl;

  for(auto p:ans) cout<<p.first<<" "<<p.second<<endl;

  return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;



typedef pair<int, int> Ginkgo;



map<int, int> sq;



int main(){

    for(int i=0; i<200; i++)

        sq[i*i] = i;

    

    int N; cin >> N;

    while(N--){

        set<Ginkgo> divs;

        int p, q; cin >> p >> q;

        for(int i=1; i<=p*p + q*q; i++){

            for(int m=-200; m<200; m++) if(i - m*m >= 0){

                int n2 = i - m*m;

                if(sq.count(n2) == 0) continue;

                

                for(auto n: {-sq[n2], sq[n2]}){

                    if((m*p+n*q)%i == 0 && (m*q-n*p)%i == 0){

                        divs.insert({n, m});

                    }

                }

            }

        }

        cout << (divs.size() == 8? "P": "C") << endl;

    }

}

// Faster C++ solution for the same problem (measured speedup: 1.6977086199535083x):
//45:00

#include <bits/stdc++.h>

using namespace std;



typedef pair<int, int> Ginkgo;



int main(){

    int N; cin >> N;

    while(N--){

        set<Ginkgo> divs;

        int p, q; cin >> p >> q;

        

        int cnt = 0;

        int l = p*p + q*q;

        for(int m=-200; m<200; m++){

            if(l < m*m) continue;

            for(int n=-200; n<200; n++){

                if(l < m*m + n*n || (n == 0 && m == 0)) continue;

                

                if((m*p+n*q)%(m*m+n*n) == 0 && (m*q-n*p)%(m*m+n*n) == 0)

                    cnt++;

            }

        }

        cout << (cnt == 8? "P": "C") << endl;

    }

}
// Slower C++ solution:
#include <bits/stdc++.h>



using namespace std;



typedef pair<int,int> P;

const int dx[] = {-1,0,0,1};

const int dy[] = {0,-1,1,0};



int main(){

  int Tc,M,N;



  cin >> Tc;

  while(Tc--){

    vector<P> vec;

    for(int i = 0 ; i < 4 ; i++){

      vec.push_back(P(dx[i],dy[i]));

    }

    cin >> M >> N;

    vec.push_back(P(M,N));

    vec.push_back(P(-N,M));

    vec.push_back(P(-M,-N));

    vec.push_back(P(N,-M));

    int cnt = 0;



    for(int m = -100 ; m <= 100 ; m++){

      for(int n = -100 ; n <= 100 ; n++){

        if(m == n && m == 0) continue;

        int X = m*m + n*n;

        if(!((m*M+n*N) % X == 0 && (m*N-n*M)%X == 0)) continue;

        int Y = (m*M+n*N)/X;

        int Z = (m*N-n*M)/X;

        if((M*M+N*N)/X == Y*Y+Z*Z){

          bool ok = true;

          for(int i = 0 ; i < 8 ; i++){

            if(vec[i].first == m && vec[i].second == n){

              ok = false;

              break;

            }

          }

          if(ok) cnt++;

        }

      }

    }

   

    if(cnt == 0) cout << "P" << endl;

    else cout << "C" << endl;

  }



  return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.8955088278709349x):
#include <bits/stdc++.h>



using namespace std;



typedef pair<int,int> P;

const int dx[] = {-1,0,0,1};

const int dy[] = {0,-1,1,0};



int main(){

  int Tc,M,N;



  cin >> Tc;

  while(Tc--){

    vector<P> vec;

    for(int i = 0 ; i < 4 ; i++){

      vec.push_back(P(dx[i],dy[i]));

    }

    cin >> M >> N;

    vec.push_back(P(M,N));

    vec.push_back(P(-N,M));

    vec.push_back(P(-M,-N));

    vec.push_back(P(N,-M));

    int cnt = 0;



    for(int m = 0 ; m <= 100 ; m++){

      for(int n = 0 ; n <= 100 ; n++){

        if(m == n && m == 0) continue;

        int X = m*m + n*n;

        if(!((m*M+n*N) % X == 0 && (m*N-n*M)%X == 0)) continue;

        int Y = (m*M+n*N)/X;

        int Z = (m*N-n*M)/X;

        if((M*M+N*N)/X == Y*Y+Z*Z){

          bool ok = true;

          for(int i = 0 ; i < 8 ; i++){

            if(vec[i].first == m && vec[i].second == n){

              ok = false;

              break;

            }

          }

          if(ok) cnt++;

        }

      }

    }

   

    if(cnt == 0) cout << "P" << endl;

    else cout << "C" << endl;

  }



  return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>



using namespace std;



typedef pair<int,int> P;

const int dx[] = {-1,0,0,1};

const int dy[] = {0,-1,1,0};



int main(){

  int Tc,M,N;



  cin >> Tc;

  while(Tc--){

    vector<P> vec;

    for(int i = 0 ; i < 4 ; i++){

      vec.push_back(P(dx[i],dy[i]));

    }

    cin >> M >> N;

    vec.push_back(P(M,N));

    vec.push_back(P(-N,M));

    vec.push_back(P(-M,-N));

    vec.push_back(P(N,-M));

    int cnt = 0;



    for(int m = -100 ; m <= 100 ; m++){

      for(int n = -100 ; n <= 100 ; n++){

        if(m == n && m == 0) continue;

        int X = m*m + n*n;

        if(!((m*M+n*N) % X == 0 && (m*N-n*M)%X == 0)) continue;

        int Y = (m*M+n*N)/X;

        int Z = (m*N-n*M)/X;

        if((M*M+N*N)/X == Y*Y+Z*Z){

          bool ok = true;

          for(int i = 0 ; i < 8 ; i++){

            if(vec[i].first == m && vec[i].second == n){

              ok = false;

              break;

            }

          }

          if(ok) cnt++;

        }

      }

    }

   

    if(cnt == 0) cout << "P" << endl;

    else cout << "C" << endl;

  }



  return 0;

}

// Faster C++ solution for the same problem (measured speedup: 2.45084974882567x):
#include <bits/stdc++.h>



using namespace std;



typedef pair<int,int> P;

const int dx[] = {-1,0,0,1};

const int dy[] = {0,-1,1,0};



int main(){

  int Tc,M,N;



  cin >> Tc;

  while(Tc--){

    vector<P> vec;

    for(int i = 0 ; i < 4 ; i++){

      vec.push_back(P(dx[i],dy[i]));

    }

    cin >> M >> N;

    vec.push_back(P(M,N));

    vec.push_back(P(-N,M));

    vec.push_back(P(-M,-N));

    vec.push_back(P(N,-M));

    int cnt = 0;



    for(int m = 0 ; m <= 50 ; m++){

      for(int n = 0 ; n <= 50 ; n++){

        if(m == n && m == 0) continue;

        int X = m*m + n*n;

        if(!((m*M+n*N) % X == 0 && (m*N-n*M)%X == 0)) continue;

        int Y = (m*M+n*N)/X;

        int Z = (m*N-n*M)/X;

        if((M*M+N*N)/X == Y*Y+Z*Z){

          bool ok = true;

          for(int i = 0 ; i < 8 ; i++){

            if(vec[i].first == m && vec[i].second == n){

              ok = false;

              break;

            }

          }

          if(ok) cnt++;

        }

      }

    }

   

    if(cnt == 0) cout << "P" << endl;

    else cout << "C" << endl;

  }



  return 0;

}