시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 85 44 40 64.516%

문제

은행수란 정수 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+XHJcblx0XHVjNzc0IFx1YjU0YywgKG0sbikgJm1pZGRvdDsgKHgseSkgPSAocCxxKVx1Yjk3YyBcdWI5Y2NcdWM4NzFcdWQ1NThcdWIyOTQgXHVjNzQwXHVkNTg5XHVjMjE4ICh4LHkpXHVhYzAwIFx1Yzg3NFx1YzdhY1x1ZDU1Y1x1YjJlNFx1YmE3NCwgKG0sbilcdWM3NDAgXHVjNzQwXHVkNTg5XHVjMjE4IChwLHEpXHVjNzU4IFx1YzU3ZFx1YzIxOFx1Yjc3Y1x1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YmFhOFx1YjRlMCAoMSwwKSwgKDAsMSksICgtMSwwKSwgKDAsLTEpLCAobSxuKSwgKC1uLG0pLCAoLW0sLW4pLCAobiwtbSlcdWM3NDAgXHVjNzg0XHVjNzU4XHVjNzU4IFx1Yzc0MFx1ZDU4OVx1YzIxOCAobSxuKVx1Yzc1OCBcdWM1N2RcdWMyMThcdWM3NzRcdWIyZTQuIFx1YjljY1x1YzU3ZCwgbTxzdXA+MjxcL3N1cD4gKyBuPHN1cD4yPFwvc3VwPiAmZ3Q7IDFcdWM3NzRcdWI3N2NcdWJhNzQsIFx1YzU1ZVx1Yzc1OCA4XHVhYzFjIFx1YzIxOFx1YjI5NCBcdWJhYThcdWI0NTAgXHViMmU0XHViOTdjIFx1YWM4M1x1Yzc3NFx1YjJlNC4gXHVjOTg5LCBtPHN1cD4yPFwvc3VwPiArIG48c3VwPjI8XC9zdXA+ICZndDsgMVx1Yzc0NCBcdWI5Y2NcdWM4NzFcdWQ1NThcdWIyOTQgXHVjNzQwXHVkNTg5XHVjMjE4XHViMjk0IFx1YzgwMVx1YzViNFx1YjNjNCA4XHVhYzFjXHVjNzU4IFx1YzU3ZFx1YzIxOFx1YWMwMCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YjljY1x1YzU3ZCwgbTxzdXA+MjxcL3N1cD4gKyBuPHN1cD4yPFwvc3VwPiAmZ3Q7IDFcdWM3NDQgXHViOWNjXHVjODcxXHVkNTU4XHViMjk0IFx1Yzc0MFx1ZDU4OVx1YzIxOCAobSxuKVx1Yzc1OCBcdWM1N2RcdWMyMThcdWFjMDAgOFx1YWMxY1x1Yjc3Y1x1YmE3NCwgXHVjNzc0IFx1YzIxOFx1Yjk3YyBcdWMxOGNcdWMyMThcdWI3N2NcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWM3NDBcdWQ1ODlcdWMyMThcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVjMThjXHVjMjE4XHVjNzc4XHVjOWMwIFx1YzU0NFx1YjJjY1x1YzljMCBcdWM1NGNcdWM1NDRcdWIwYjRcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlxyXG5cdFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWFjMWNcdWMyMThcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBcdWQ1NWMgXHVjOTA0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWM3M2NcdWJhNzAsIFx1Yzc0MFx1ZDU4OVx1YzIxOCAobSxuKVx1Yzc1OCBtXHVhY2ZjIG5cdWM3NzQgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1YjQxOFx1YzViNCBcdWM3ODhcdWIyZTQuICgxICZsdDsgbTxzdXA+MjxcL3N1cD4gKyBuPHN1cD4yPFwvc3VwPiAmbHQ7IDIwMDAwKTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlxyXG5cdFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYywgXHVjNzg1XHViODI1XHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljNCBcdWM3NDBcdWQ1ODlcdWMyMThcdWFjMDAgXHVjMThjXHVjMjE4XHViNzdjXHViYTc0IFBcdWI5N2MsIFx1YzU0NFx1YjJjOFx1Yjc3Y1x1YmE3NCBDXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiPHA+XHJcblx0bTxzdXA+MjxcL3N1cD4gKyBuPHN1cD4yPFwvc3VwPiAmZ3Q7IDBcdWM3NzggXHVhY2JkXHVjNmIwXHVjNWQwIG08c3VwPjI8XC9zdXA+ICsgbjxzdXA+MjxcL3N1cD5cdWM3NzQgbXAgKyBucVx1YzY0MCBtcSAtIG5wXHVjNzU4IFx1YWNmNVx1YzU3ZFx1YzIxOFx1Yjc3Y1x1YmE3NCwgKG0sbilcdWM3NDAgKHAscSlcdWM3NTggXHVjNTdkXHVjMjE4XHVjNzc0XHVhY2UwLCBcdWFkZjggXHVjNWVkXHViM2M0IFx1YzEzMVx1YjliZFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG48cD5cclxuXHRcdWI5Y2NcdWM1N2QsIChtLG4pICZtaWRkb3Q7ICh4LHkpID0gKHAscSlcdWI3N2NcdWJhNzQsIChtPHN1cD4yPFwvc3VwPiArIG48c3VwPjI8XC9zdXA+KSh4PHN1cD4yPFwvc3VwPiArIHk8c3VwPjI8XC9zdXA+KSA9IHA8c3VwPjI8XC9zdXA+ICsgcTxzdXA+MjxcL3N1cD5cdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIzODI1IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiR2lua2dvIE51bWJlcnMiLCJkZXNjcmlwdGlvbiI6IjxwPldlIHdpbGwgZGUgbmUgR2lua2dvIG51bWJlcnMgYW5kIG11bHRpcGxpY2F0aW9uIG9uIEdpbmtnbyBudW1iZXJzLjxcL3A+XHJcblxyXG48cD5BIEdpbmtnbyBudW1iZXIgaXMgYSBwYWlyICZsYW5nO20sIG4mcmFuZzsgd2hlcmUgbSBhbmQgbiBhcmUgaW50ZWdlcnMuIEZvciBleGFtcGxlLCAmbGFuZzsxLCAxJnJhbmc7LCAmbGFuZzstMiwgMSZyYW5nOyBhbmQgJmxhbmc7LTMsIC0xJnJhbmc7IGFyZSBHaW5rZ28gbnVtYmVycy48XC9wPlxyXG5cclxuPHA+VGhlIG11bHRpcGxpY2F0aW9uIG9uIEdpbmtnbyBudW1iZXJzIGlzIGRlIG5lZCBieSAmbGFuZzttLCBuJnJhbmc7ICZtaWRkb3Q7ICZsYW5nO3gsIHkmcmFuZzsgPSAmbGFuZztteCAtJm5ic3A7bnksIG15ICsgbngmcmFuZzsuIEZvciBleGFtcGxlLCAmbGFuZzsxLCAxJnJhbmc7ICZtaWRkb3Q7ICZsYW5nOy0yLCAxJnJhbmc7ID0gJmxhbmc7LTMsIC0xJnJhbmc7LjxcL3A+XHJcblxyXG48cD5BIEdpbmtnbyBudW1iZXIgJmxhbmc7bSwgbiZyYW5nOyBpcyBjYWxsZWQgYSBkaXZpc29yIG9mIGEgR2lua2dvIG51bWJlciAmbGFuZztwLCBxJnJhbmc7IGlmIHRoZXJlIGV4aXN0cyBhIEdpbmtnbyBudW1iZXIgJmxhbmc7eCwgeSZyYW5nOyBzdWNoIHRoYXQgJmxhbmc7bSwgbiZyYW5nOyAmbWlkZG90OyAmbGFuZzt4LCB5JnJhbmc7ID0gJmxhbmc7cCwgcSZyYW5nOy48XC9wPlxyXG5cclxuPHA+Rm9yIGFueSBHaW5rZ28gbnVtYmVyICZsYW5nO20sIG4mcmFuZzssIEdpbmtnbyBudW1iZXJzICZsYW5nOzEsIDAmcmFuZzssICZsYW5nOzAsIDEmcmFuZzssICZsYW5nOy0xLCAwJnJhbmc7LCAmbGFuZzswLCAtMSZyYW5nOywgJmxhbmc7bSwgbiZyYW5nOywgJmxhbmc7LW4sIG0mcmFuZzssICZsYW5nOy1tLCAtbiZyYW5nOyBhbmQgJmxhbmc7LW4sIC1tJnJhbmc7IGFyZSBkaXZpc29ycyBvZiAmbGFuZzttLCBuJnJhbmc7LiBJZiBtPHN1cD4yPFwvc3VwPiArIG48c3VwPjI8XC9zdXA+ICZndDsgMSwgdGhlc2UgR2lua2dvIG51bWJlcnMgYXJlIGRpc3RpbmN0LiBJbiBvdGhlciB3b3JkcywgYW55IEdpbmtnbyBudW1iZXIgc3VjaCB0aGF0IG08c3VwPjI8XC9zdXA+ICsgbjxzdXA+MjxcL3N1cD4gJmd0OyAxIGhhcyBhdCBsZWFzdCBlaWdodCBkaXZpc29ycy48XC9wPlxyXG5cclxuPHA+QSBHaW5rZ28gbnVtYmVyICZsYW5nO20sIG4mcmFuZzsgaXMgY2FsbGVkIGEgcHJpbWUgaWYgbTxzdXA+MjxcL3N1cD4gKyBuPHN1cD4yPFwvc3VwPiAmZ3Q7IDEgYW5kIGl0IGhhcyBleGFjdGx5IGVpZ2h0IGRpdmlzb3JzLiBZb3VyIG1pc3Npb24gaXMgdG8gY2hlY2sgd2hldGhlciBhIGdpdmVuIEdpbmtnbyBudW1iZXIgaXMgYSBwcmltZSBvciBub3QuPFwvcD5cclxuXHJcbjxwPlRoZSBmb2xsb3dpbmcgdHdvIGZhY3RzIG1pZ2h0IGJlIHVzZWZ1bCB0byBjaGVjayB3aGV0aGVyIGEgR2lua2dvIG51bWJlciBpcyBhIGRpdmlzb3Igb2YgYW5vdGhlciBHaW5rZ28gbnVtYmVyLjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPlN1cHBvc2UgbTxzdXA+MjxcL3N1cD4gKyBuPHN1cD4yPFwvc3VwPiAmZ3Q7IDAuIFRoZW4sICZsYW5nO20sIG4mcmFuZzsgaXMgYSBkaXZpc29yIG9mICZsYW5nO3AsIHEmcmFuZzsgaWYgYW5kIG9ubHkgaWYgdGhlIGludGVnZXIgbTxzdXA+MjxcL3N1cD4gKyBuPHN1cD4yPFwvc3VwPiBpcyBhIGNvbW1vbiBkaXZpc29yIG9mIG1wICsgbnEgYW5kIG1xIC0gbnAuPFwvbGk+XHJcblx0PGxpPklmICZsYW5nO20sIG4mcmFuZzsgJm1pZGRvdDsgJmxhbmc7eCwgeSZyYW5nOyA9ICZsYW5nO3AsIHEmcmFuZzssIHRoZW4gKG08c3VwPjI8XC9zdXA+ICsgbjxzdXA+MjxcL3N1cD4pKHg8c3VwPjI8XC9zdXA+ICsgeTxzdXA+MjxcL3N1cD4pID0gcDxzdXA+MjxcL3N1cD4gKyBxPHN1cD4yPFwvc3VwPi48XC9saT5cclxuPFwvdWw+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgdGhlIGlucHV0IGNvbnRhaW5zIGEgc2luZ2xlIGludGVnZXIsIHdoaWNoIGlzIHRoZSBudW1iZXIgb2YgZGF0YXNldHMuPFwvcD5cclxuXHJcbjxwPlRoZSByZXN0IG9mIHRoZSBpbnB1dCBpcyBhIHNlcXVlbmNlIG9mIGRhdGFzZXRzLiBFYWNoIGRhdGFzZXQgaXMgYSBsaW5lIGNvbnRhaW5pbmcgdHdvIGludGVnZXJzIG0gYW5kIG4sIHNlcGFyYXRlZCBieSBhIHNwYWNlLiBUaGV5IGRlc2lnbmF0ZSB0aGUgR2lua2dvIG51bWJlciAmbGFuZzttLCBuJnJhbmc7LiBZb3UgY2FuIGFzc3VtZSAxICZsdDsgbTxzdXA+MjxcL3N1cD4gKyBuPHN1cD4yPFwvc3VwPiAmbHQ7IDIwMDAwLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIGRhdGFzZXQsIG91dHB1dCBhIGNoYXJhY3RlciBgUCYjMzk7IGluIGEgbGluZSBpZiB0aGUgR2lua2dvIG51bWJlciBpcyBhIHByaW1lLiBPdXRwdXQgYSBjaGFyYWN0ZXIgYEMmIzM5OyBpbiBhIGxpbmUgb3RoZXJ3aXNlLjxcL3A+XHJcbiIsImhpbnQiOiI8cD5Gb3IgZWFjaCBkYXRhc2V0LCBvdXRwdXQgYSBjaGFyYWN0ZXIgYFAmIzM5OyBpbiBhIGxpbmUgaWYgdGhlIEdpbmtnbyBudW1iZXIgaXMgYSBwcmltZS4gT3V0cHV0IGEgY2hhcmFjdGVyIGBDJiMzOTsgaW4gYSBsaW5lIG90aGVyd2lzZS48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

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