시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 91 45 41 65.079%

문제

은행수란 정수 m과 n의 쌍 (m,n)이다. 예를 들어, (1,1), (-2,1), (-3,-1)은 은행수이다.

은행수의 곱셈 (m,n) · (x,y) = (mx - ny, my + nx) 이다. 예를 들어, (1,1)·(-2,1) = (-3,-1)이다.

이때, (m,n) · (x,y) = (p,q)를 만족하는 은행수 (x,y)가 존재한다면, (m,n)은 은행수 (p,q)의 약수라고 한다.

모든 (1,0), (0,1), (-1,0), (0,-1), (m,n), (-n,m), (-m,-n), (n,-m)은 임의의 은행수 (m,n)의 약수이다. 만약, m2 + n2 > 1이라면, 앞의 8개 수는 모두 다를 것이다. 즉, m2 + n2 > 1을 만족하는 은행수는 적어도 8개의 약수가 있다.

만약, m2 + n2 > 1을 만족하는 은행수 (m,n)의 약수가 8개라면, 이 수를 소수라고 한다.

은행수가 주어졌을 때, 소수인지 아닌지 알아내는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있으며, 은행수 (m,n)의 m과 n이 공백으로 구분되어 있다. (1 < m2 + n2 < 20000)

출력

각 테스트 케이스에 대해서, 입력으로 주어진 은행수가 소수라면 P를, 아니라면 C를 출력한다.

예제 입력 1

8
10 0
0 2
-3 0
4 2
0 -13
-4 1
-2 -1
3 -1

예제 출력 1

C
C
P
C
C
P
P
C

힌트

m2 + n2 > 0인 경우에 m2 + n2이 mp + nq와 mq - np의 공약수라면, (m,n)은 (p,q)의 약수이고, 그 역도 성립한다.

만약, (m,n) · (x,y) = (p,q)라면, (m2 + n2)(x2 + y2) = p2 + q2이다.

W3sicHJvYmxlbV9pZCI6IjM4MjUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM3NDBcdWQ1ODlcdWMyMTgiLCJkZXNjcmlwdGlvbiI6IjxwPlxyXG5cdFx1Yzc0MFx1ZDU4OVx1YzIxOFx1Yjc4MCBcdWM4MTVcdWMyMTggbVx1YWNmYyBuXHVjNzU4IFx1YzMwZCAobSxuKVx1Yzc3NFx1YjJlNC4gXHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgKDEsMSksICgtMiwxKSwgKC0zLC0xKVx1Yzc0MCBcdWM3NDBcdWQ1ODlcdWMyMThcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1Yzc0MFx1ZDU4OVx1YzIxOFx1Yzc1OCBcdWFjZjFcdWMxNDggKG0sbikgJm1pZGRvdDsgKHgseSkgPSAobXggLSBueSwgbXkgKyBueCkgXHVjNzc0XHViMmU0LiBcdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCAoMSwxKSZtaWRkb3Q7KC0yLDEpID0gKC0zLC0xKVx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHVjNzc0XHViNTRjLCAobSxuKSAmbWlkZG90OyAoeCx5KSA9IChwLHEpXHViOTdjIFx1YjljY1x1Yzg3MVx1ZDU1OFx1YjI5NCBcdWM3NDBcdWQ1ODlcdWMyMTggKHgseSlcdWFjMDAgXHVjODc0XHVjN2FjXHVkNTVjXHViMmU0XHViYTc0LCAobSxuKVx1Yzc0MCBcdWM3NDBcdWQ1ODlcdWMyMTggKHAscSlcdWM3NTggXHVjNTdkXHVjMjE4XHViNzdjXHVhY2UwIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHViYWE4XHViNGUwICgxLDApLCAoMCwxKSwgKC0xLDApLCAoMCwtMSksIChtLG4pLCAoLW4sbSksICgtbSwtbiksIChuLC1tKVx1Yzc0MCBcdWM3ODRcdWM3NThcdWM3NTggXHVjNzQwXHVkNTg5XHVjMjE4IChtLG4pXHVjNzU4IFx1YzU3ZFx1YzIxOFx1Yzc3NFx1YjJlNC4gXHViOWNjXHVjNTdkLCBtPHN1cD4yPFwvc3VwPiArIG48c3VwPjI8XC9zdXA+ICZndDsgMVx1Yzc3NFx1Yjc3Y1x1YmE3NCwgXHVjNTVlXHVjNzU4IDhcdWFjMWMgXHVjMjE4XHViMjk0IFx1YmFhOFx1YjQ1MCBcdWIyZTRcdWI5N2MgXHVhYzgzXHVjNzc0XHViMmU0LiBcdWM5ODksIG08c3VwPjI8XC9zdXA+ICsgbjxzdXA+MjxcL3N1cD4gJmd0OyAxXHVjNzQ0IFx1YjljY1x1Yzg3MVx1ZDU1OFx1YjI5NCBcdWM3NDBcdWQ1ODlcdWMyMThcdWIyOTQgXHVjODAxXHVjNWI0XHViM2M0IDhcdWFjMWNcdWM3NTggXHVjNTdkXHVjMjE4XHVhYzAwIFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHViOWNjXHVjNTdkLCBtPHN1cD4yPFwvc3VwPiArIG48c3VwPjI8XC9zdXA+ICZndDsgMVx1Yzc0NCBcdWI5Y2NcdWM4NzFcdWQ1NThcdWIyOTQgXHVjNzQwXHVkNTg5XHVjMjE4IChtLG4pXHVjNzU4IFx1YzU3ZFx1YzIxOFx1YWMwMCA4XHVhYzFjXHViNzdjXHViYTc0LCBcdWM3NzQgXHVjMjE4XHViOTdjIFx1YzE4Y1x1YzIxOFx1Yjc3Y1x1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1Yzc0MFx1ZDU4OVx1YzIxOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWMxOGNcdWMyMThcdWM3NzhcdWM5YzAgXHVjNTQ0XHViMmNjXHVjOWMwIFx1YzU0Y1x1YzU0NFx1YjBiNFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHJcblx0XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YWMxY1x1YzIxOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViMjk0IFx1ZDU1YyBcdWM5MDRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YzczY1x1YmE3MCwgXHVjNzQwXHVkNTg5XHVjMjE4IChtLG4pXHVjNzU4IG1cdWFjZmMgblx1Yzc3NCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHViNDE4XHVjNWI0IFx1Yzc4OFx1YjJlNC4gKDEgJmx0OyBtPHN1cD4yPFwvc3VwPiArIG48c3VwPjI8XC9zdXA+ICZsdDsgMjAwMDApPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHJcblx0XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjLCBcdWM3ODVcdWI4MjVcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0IFx1Yzc0MFx1ZDU4OVx1YzIxOFx1YWMwMCBcdWMxOGNcdWMyMThcdWI3N2NcdWJhNzQgUFx1Yjk3YywgXHVjNTQ0XHViMmM4XHViNzdjXHViYTc0IENcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiI8cD5cclxuXHRtPHN1cD4yPFwvc3VwPiArIG48c3VwPjI8XC9zdXA+ICZndDsgMFx1Yzc3OCBcdWFjYmRcdWM2YjBcdWM1ZDAgbTxzdXA+MjxcL3N1cD4gKyBuPHN1cD4yPFwvc3VwPlx1Yzc3NCBtcCArIG5xXHVjNjQwIG1xIC0gbnBcdWM3NTggXHVhY2Y1XHVjNTdkXHVjMjE4XHViNzdjXHViYTc0LCAobSxuKVx1Yzc0MCAocCxxKVx1Yzc1OCBcdWM1N2RcdWMyMThcdWM3NzRcdWFjZTAsIFx1YWRmOCBcdWM1ZWRcdWIzYzQgXHVjMTMxXHViOWJkXHVkNTVjXHViMmU0LjxcL3A+XHJcbjxwPlxyXG5cdFx1YjljY1x1YzU3ZCwgKG0sbikgJm1pZGRvdDsgKHgseSkgPSAocCxxKVx1Yjc3Y1x1YmE3NCwgKG08c3VwPjI8XC9zdXA+ICsgbjxzdXA+MjxcL3N1cD4pKHg8c3VwPjI8XC9zdXA+ICsgeTxzdXA+MjxcL3N1cD4pID0gcDxzdXA+MjxcL3N1cD4gKyBxPHN1cD4yPFwvc3VwPlx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjM4MjUiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJHaW5rZ28gTnVtYmVycyIsImRlc2NyaXB0aW9uIjoiPHA+V2Ugd2lsbCBkZSBuZSBHaW5rZ28gbnVtYmVycyBhbmQgbXVsdGlwbGljYXRpb24gb24gR2lua2dvIG51bWJlcnMuPFwvcD5cclxuXHJcbjxwPkEgR2lua2dvIG51bWJlciBpcyBhIHBhaXIgJmxhbmc7bSwgbiZyYW5nOyB3aGVyZSBtIGFuZCBuIGFyZSBpbnRlZ2Vycy4gRm9yIGV4YW1wbGUsICZsYW5nOzEsIDEmcmFuZzssICZsYW5nOy0yLCAxJnJhbmc7IGFuZCAmbGFuZzstMywgLTEmcmFuZzsgYXJlIEdpbmtnbyBudW1iZXJzLjxcL3A+XHJcblxyXG48cD5UaGUgbXVsdGlwbGljYXRpb24gb24gR2lua2dvIG51bWJlcnMgaXMgZGUgbmVkIGJ5ICZsYW5nO20sIG4mcmFuZzsgJm1pZGRvdDsgJmxhbmc7eCwgeSZyYW5nOyA9ICZsYW5nO214IC0mbmJzcDtueSwgbXkgKyBueCZyYW5nOy4gRm9yIGV4YW1wbGUsICZsYW5nOzEsIDEmcmFuZzsgJm1pZGRvdDsgJmxhbmc7LTIsIDEmcmFuZzsgPSAmbGFuZzstMywgLTEmcmFuZzsuPFwvcD5cclxuXHJcbjxwPkEgR2lua2dvIG51bWJlciAmbGFuZzttLCBuJnJhbmc7IGlzIGNhbGxlZCBhIGRpdmlzb3Igb2YgYSBHaW5rZ28gbnVtYmVyICZsYW5nO3AsIHEmcmFuZzsgaWYgdGhlcmUgZXhpc3RzIGEgR2lua2dvIG51bWJlciAmbGFuZzt4LCB5JnJhbmc7IHN1Y2ggdGhhdCAmbGFuZzttLCBuJnJhbmc7ICZtaWRkb3Q7ICZsYW5nO3gsIHkmcmFuZzsgPSAmbGFuZztwLCBxJnJhbmc7LjxcL3A+XHJcblxyXG48cD5Gb3IgYW55IEdpbmtnbyBudW1iZXIgJmxhbmc7bSwgbiZyYW5nOywgR2lua2dvIG51bWJlcnMgJmxhbmc7MSwgMCZyYW5nOywgJmxhbmc7MCwgMSZyYW5nOywgJmxhbmc7LTEsIDAmcmFuZzssICZsYW5nOzAsIC0xJnJhbmc7LCAmbGFuZzttLCBuJnJhbmc7LCAmbGFuZzstbiwgbSZyYW5nOywgJmxhbmc7LW0sIC1uJnJhbmc7IGFuZCAmbGFuZzstbiwgLW0mcmFuZzsgYXJlIGRpdmlzb3JzIG9mICZsYW5nO20sIG4mcmFuZzsuIElmIG08c3VwPjI8XC9zdXA+ICsgbjxzdXA+MjxcL3N1cD4gJmd0OyAxLCB0aGVzZSBHaW5rZ28gbnVtYmVycyBhcmUgZGlzdGluY3QuIEluIG90aGVyIHdvcmRzLCBhbnkgR2lua2dvIG51bWJlciBzdWNoIHRoYXQgbTxzdXA+MjxcL3N1cD4gKyBuPHN1cD4yPFwvc3VwPiAmZ3Q7IDEgaGFzIGF0IGxlYXN0IGVpZ2h0IGRpdmlzb3JzLjxcL3A+XHJcblxyXG48cD5BIEdpbmtnbyBudW1iZXIgJmxhbmc7bSwgbiZyYW5nOyBpcyBjYWxsZWQgYSBwcmltZSBpZiBtPHN1cD4yPFwvc3VwPiArIG48c3VwPjI8XC9zdXA+ICZndDsgMSBhbmQgaXQgaGFzIGV4YWN0bHkgZWlnaHQgZGl2aXNvcnMuIFlvdXIgbWlzc2lvbiBpcyB0byBjaGVjayB3aGV0aGVyIGEgZ2l2ZW4gR2lua2dvIG51bWJlciBpcyBhIHByaW1lIG9yIG5vdC48XC9wPlxyXG5cclxuPHA+VGhlIGZvbGxvd2luZyB0d28gZmFjdHMgbWlnaHQgYmUgdXNlZnVsIHRvIGNoZWNrIHdoZXRoZXIgYSBHaW5rZ28gbnVtYmVyIGlzIGEgZGl2aXNvciBvZiBhbm90aGVyIEdpbmtnbyBudW1iZXIuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+U3VwcG9zZSBtPHN1cD4yPFwvc3VwPiArIG48c3VwPjI8XC9zdXA+ICZndDsgMC4gVGhlbiwgJmxhbmc7bSwgbiZyYW5nOyBpcyBhIGRpdmlzb3Igb2YgJmxhbmc7cCwgcSZyYW5nOyBpZiBhbmQgb25seSBpZiB0aGUgaW50ZWdlciBtPHN1cD4yPFwvc3VwPiArIG48c3VwPjI8XC9zdXA+IGlzIGEgY29tbW9uIGRpdmlzb3Igb2YgbXAgKyBucSBhbmQgbXEgLSBucC48XC9saT5cclxuXHQ8bGk+SWYgJmxhbmc7bSwgbiZyYW5nOyAmbWlkZG90OyAmbGFuZzt4LCB5JnJhbmc7ID0gJmxhbmc7cCwgcSZyYW5nOywgdGhlbiAobTxzdXA+MjxcL3N1cD4gKyBuPHN1cD4yPFwvc3VwPikoeDxzdXA+MjxcL3N1cD4gKyB5PHN1cD4yPFwvc3VwPikgPSBwPHN1cD4yPFwvc3VwPiArIHE8c3VwPjI8XC9zdXA+LjxcL2xpPlxyXG48XC91bD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiB0aGUgaW5wdXQgY29udGFpbnMgYSBzaW5nbGUgaW50ZWdlciwgd2hpY2ggaXMgdGhlIG51bWJlciBvZiBkYXRhc2V0cy48XC9wPlxyXG5cclxuPHA+VGhlIHJlc3Qgb2YgdGhlIGlucHV0IGlzIGEgc2VxdWVuY2Ugb2YgZGF0YXNldHMuIEVhY2ggZGF0YXNldCBpcyBhIGxpbmUgY29udGFpbmluZyB0d28gaW50ZWdlcnMgbSBhbmQgbiwgc2VwYXJhdGVkIGJ5IGEgc3BhY2UuIFRoZXkgZGVzaWduYXRlIHRoZSBHaW5rZ28gbnVtYmVyICZsYW5nO20sIG4mcmFuZzsuIFlvdSBjYW4gYXNzdW1lIDEgJmx0OyBtPHN1cD4yPFwvc3VwPiArIG48c3VwPjI8XC9zdXA+ICZsdDsgMjAwMDAuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggZGF0YXNldCwgb3V0cHV0IGEgY2hhcmFjdGVyIGBQJiMzOTsgaW4gYSBsaW5lIGlmIHRoZSBHaW5rZ28gbnVtYmVyIGlzIGEgcHJpbWUuIE91dHB1dCBhIGNoYXJhY3RlciBgQyYjMzk7IGluIGEgbGluZSBvdGhlcndpc2UuPFwvcD5cclxuIiwiaGludCI6IjxwPkZvciBlYWNoIGRhdGFzZXQsIG91dHB1dCBhIGNoYXJhY3RlciBgUCYjMzk7IGluIGEgbGluZSBpZiB0aGUgR2lua2dvIG51bWJlciBpcyBhIHByaW1lLiBPdXRwdXQgYSBjaGFyYWN0ZXIgYEMmIzM5OyBpbiBhIGxpbmUgb3RoZXJ3aXNlLjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

ACM-ICPC > Regionals > Asia > Japan > Asia Regional Contest 2012 in Tokyo A번