시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 256 MB150058144037.704%

문제

Q. : 아래의 수열에서 다음에 올 수를 찾으시오.

313 331 367 ...

경복 : ??

강산 : 379.

경복 : 뭐?

강산 : 행복한 소수잖아.

경복 : 행복한 뭐?

강산 : 그러니까, 자리수의 제곱의 합을 구하는 연산을 계속 반복했을 때 1이 되는 수를 행복한 수라고 하잖아. 행복한 소수는 그 중 소수인 수이고.

7은 분명 소수이다. 과연 행복할까?

  • 7 → 72 = 49
  • 49 → 42 + 92 = 97
  • 97 → 92 + 72 = 130
  • 130 → 12 + 32 + 02 = 10
  • 10 → 12 + 02 = 1

7은 행복한 수이다 ☺.

사실 7은 행복한 소수 중 가장 작은 수이다. (이 문제에서는 1을 소수가 아닌 것으로 생각한다)

어떤 수가 주어지면 이 수가 행복한 소수인지 판정해보자.

입력

첫 줄에 테스트 케이스의 수 P가 주어진다. (1 ≤ P ≤ 1000)

각 테스트 케이스는 테스트 케이스 번호와 행복한 소수인지 판정해야 할 정수인 M으로 이루어져 있다. (1 ≤ m ≤ 10000).

 

출력

각 테스트 케이스마다, 테스트 케이스의 번호, 입력받은 수, 만일 M이 행복한 소수라면 YES 아니라면 NO를 공백으로 각각 구분하여 출력한다.

예제 입력 1

4
1 1
2 7
3 383
4 1000

예제 출력 1

1 1 NO
2 7 YES
3 383 YES
4 1000 NO
W3sicHJvYmxlbV9pZCI6IjEwNDM0IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVkNTg5XHViY2Y1XHVkNTVjIFx1YzE4Y1x1YzIxOCIsImRlc2NyaXB0aW9uIjoiPHA+US4gOiBcdWM1NDRcdWI3OThcdWM3NTggXHVjMjE4XHVjNWY0XHVjNWQwXHVjMTFjIFx1YjJlNFx1Yzc0Y1x1YzVkMCBcdWM2MmMgXHVjMjE4XHViOTdjIFx1Y2MzZVx1YzczY1x1YzJkY1x1YzYyNC48XC9wPlxyXG5cclxuPHA+MzEzIDMzMSAzNjcgLi4uPFwvcD5cclxuXHJcbjxwPlx1YWNiZFx1YmNmNSA6ID8/PFwvcD5cclxuXHJcbjxwPlx1YWMxNVx1YzBiMCA6IDM3OS48XC9wPlxyXG5cclxuPHA+XHVhY2JkXHViY2Y1IDogXHViYjUwPzxcL3A+XHJcblxyXG48cD5cdWFjMTVcdWMwYjAgOiBcdWQ1ODlcdWJjZjVcdWQ1NWMgXHVjMThjXHVjMjE4XHVjNzk2XHVjNTQ0LjxcL3A+XHJcblxyXG48cD5cdWFjYmRcdWJjZjUgOiBcdWQ1ODlcdWJjZjVcdWQ1NWMgXHViYjUwPzxcL3A+XHJcblxyXG48cD5cdWFjMTVcdWMwYjAgOiBcdWFkZjhcdWI3ZWNcdWIyYzhcdWFlNGMsIFx1Yzc5MFx1YjlhY1x1YzIxOFx1Yzc1OCBcdWM4MWNcdWFjZjFcdWM3NTggXHVkNTY5XHVjNzQ0IFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWM1ZjBcdWMwYjBcdWM3NDQgXHVhY2M0XHVjMThkIFx1YmMxOFx1YmNmNVx1ZDU4OFx1Yzc0NCBcdWI1NGMgMVx1Yzc3NCBcdWI0MThcdWIyOTQgXHVjMjE4XHViOTdjIFx1ZDU4OVx1YmNmNVx1ZDU1YyBcdWMyMThcdWI3N2NcdWFjZTAgXHVkNTU4XHVjNzk2XHVjNTQ0LiBcdWQ1ODlcdWJjZjVcdWQ1NWMgXHVjMThjXHVjMjE4XHViMjk0IFx1YWRmOCBcdWM5MTEgXHVjMThjXHVjMjE4XHVjNzc4IFx1YzIxOFx1Yzc3NFx1YWNlMC48XC9wPlxyXG5cclxuPHA+N1x1Yzc0MCBcdWJkODRcdWJhODUgXHVjMThjXHVjMjE4XHVjNzc0XHViMmU0LiBcdWFjZmNcdWM1ZjAgXHVkNTg5XHViY2Y1XHVkNTYwXHVhZTRjPzxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPjcgJnJhcnI7IDc8c3VwPjI8XC9zdXA+ID0gNDk8XC9saT5cclxuXHQ8bGk+NDkgJnJhcnI7IDQ8c3VwPjI8XC9zdXA+ICsgOTxzdXA+MjxcL3N1cD4gPSA5NzxcL2xpPlxyXG5cdDxsaT45NyAmcmFycjsgOTxzdXA+MjxcL3N1cD4gKyA3PHN1cD4yPFwvc3VwPiA9IDEzMDxcL2xpPlxyXG5cdDxsaT4xMzAgJnJhcnI7IDE8c3VwPjI8XC9zdXA+ICsgMzxzdXA+MjxcL3N1cD4gKyAwPHN1cD4yPFwvc3VwPiA9IDEwPFwvbGk+XHJcblx0PGxpPjEwICZyYXJyOyAxPHN1cD4yPFwvc3VwPiArIDA8c3VwPjI8XC9zdXA+ID0gMTxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPjdcdWM3NDAgXHVkNTg5XHViY2Y1XHVkNTVjIFx1YzIxOFx1Yzc3NFx1YjJlNCBcdTI2M2EuPFwvcD5cclxuXHJcbjxwPlx1YzBhY1x1YzJlNCA3XHVjNzQwIFx1ZDU4OVx1YmNmNVx1ZDU1YyBcdWMxOGNcdWMyMTggXHVjOTExIFx1YWMwMFx1YzdhNSBcdWM3OTFcdWM3NDAgXHVjMjE4XHVjNzc0XHViMmU0LiAoXHVjNzc0IFx1YmIzOFx1YzgxY1x1YzVkMFx1YzExY1x1YjI5NCAxXHVjNzQ0IFx1YzE4Y1x1YzIxOFx1YWMwMCBcdWM1NDRcdWIyY2MgXHVhYzgzXHVjNzNjXHViODVjIFx1YzBkZFx1YWMwMVx1ZDU1Y1x1YjJlNCk8XC9wPlxyXG5cclxuPHA+XHVjNWI0XHViNWE0IFx1YzIxOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWJhNzQgXHVjNzc0IFx1YzIxOFx1YWMwMCBcdWQ1ODlcdWJjZjVcdWQ1NWMgXHVjMThjXHVjMjE4XHVjNzc4XHVjOWMwIFx1ZDMxMFx1YzgxNVx1ZDU3NFx1YmNmNFx1Yzc5MC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYiBcdWM5MDRcdWM1ZDAgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWMyMTggUFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgUCAmbGU7IDEwMDApPFwvcD5cclxuXHJcbjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViMjk0IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTQgXHViYzg4XHVkNjM4XHVjNjQwIFx1ZDU4OVx1YmNmNVx1ZDU1YyBcdWMxOGNcdWMyMThcdWM3NzhcdWM5YzAgXHVkMzEwXHVjODE1XHVkNTc0XHVjNTdjIFx1ZDU2MCBcdWM4MTVcdWMyMThcdWM3NzggTVx1YzczY1x1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiAoMSAmbGU7IG0gJmxlOyAxMDAwMCkuPFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViOWM4XHViMmU0LCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YmM4OFx1ZDYzOCwgXHVjNzg1XHViODI1XHViYzFiXHVjNzQwIFx1YzIxOCwgXHViOWNjXHVjNzdjIE1cdWM3NzQgXHVkNTg5XHViY2Y1XHVkNTVjIFx1YzE4Y1x1YzIxOFx1Yjc3Y1x1YmE3NCBZRVMgXHVjNTQ0XHViMmM4XHViNzdjXHViYTc0IE5PXHViOTdjIFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFjMDFcdWFjMDEgXHVhZDZjXHViZDg0XHVkNTU4XHVjNWVjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIxMDQzNCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkhhcHB5IEhhcHB5IFByaW1lIFByaW1lIiwiZGVzY3JpcHRpb24iOiI8cD5SaWxleSBWYXNodGVlOiBbcmVhZGluZyBmcm9tIGRpc3BsYXldIEZpbmQgdGhlIG5leHQgbnVtYmVyIGluIHRoZSBzZXF1ZW5jZTo8XC9wPlxyXG5cclxuPHA+MzEzIDMzMSAzNjcgLi4uPyBXaGF0PzxcL3A+XHJcblxyXG48cD5UaGUgRG9jdG9yOiAzNzkuPFwvcD5cclxuXHJcbjxwPk1hcnRoYSBKb25lczogV2hhdD88XC9wPlxyXG5cclxuPHA+VGhlIERvY3RvcjogSXQmIzM5O3MgYSBzZXF1ZW5jZSBvZiBoYXBweSBwcmltZXMgLSAzNzkuPFwvcD5cclxuXHJcbjxwPk1hcnRoYSBKb25lczogSGFwcHkgd2hhdD88XC9wPlxyXG5cclxuPHA+VGhlIERvY3RvcjogQW55IG51bWJlciB0aGF0IHJlZHVjZXMgdG8gb25lIHdoZW4geW91IHRha2UgdGhlIHN1bSBvZiB0aGUgc3F1YXJlIG9mIGl0cyBkaWdpdHMgYW5kIGNvbnRpbnVlIGl0ZXJhdGluZyBpdCB1bnRpbCBpdCB5aWVsZHMgMSBpcyBhIGhhcHB5IG51bWJlci4gQW55IG51bWJlciB0aGF0IGRvZXNuJiMzOTt0LCBpc24mIzM5O3QuIEEgaGFwcHkgcHJpbWUgaXMgYm90aCBoYXBweSBhbmQgcHJpbWUuPFwvcD5cclxuXHJcbjxwPlRoZSBEb2N0b3I6IEkgZHVubm8sIHRhbGsgYWJvdXQgZHVtYmluZyBkb3duLiBEb24mIzM5O3QgdGhleSB0ZWFjaCByZWNyZWF0aW9uYWwgbWF0aGVtYXRpY3MgYW55bW9yZT88XC9wPlxyXG5cclxuPHA+RXhjZXJwdGVkIGZyb20gJnF1b3Q7RHIuIFdobyZxdW90OywgRXBpc29kZSA0MiAoMjAwNykuPFwvcD5cclxuXHJcbjxwPlRoZSBudW1iZXIgNyBpcyBjZXJ0YWlubHkgcHJpbWUuIEJ1dCBpcyBpdCBoYXBweT88XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT43ICZyYXJyOyA3PHN1cD4yPFwvc3VwPiA9IDQ5PFwvbGk+XHJcblx0PGxpPjQ5ICZyYXJyOyA0PHN1cD4yPFwvc3VwPiArIDk8c3VwPjI8XC9zdXA+ID0gOTc8XC9saT5cclxuXHQ8bGk+OTcgJnJhcnI7IDk8c3VwPjI8XC9zdXA+ICsgNzxzdXA+MjxcL3N1cD4gPSAxMzA8XC9saT5cclxuXHQ8bGk+MTMwICZyYXJyOyAxPHN1cD4yPFwvc3VwPiArIDM8c3VwPjI8XC9zdXA+ID0gMTA8XC9saT5cclxuXHQ8bGk+MTAgJnJhcnI7IDE8c3VwPjI8XC9zdXA+ICsgMDxzdXA+MjxcL3N1cD4gPSAxPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+SXQgaXMgaGFwcHkgXHUyNjNhLiBBcyBpdCBoYXBwZW5zLCA3IGlzIHRoZSBzbWFsbGVzdCBoYXBweSBwcmltZS4gUGxlYXNlIG5vdGUgdGhhdCBmb3IgdGhlIHB1cnBvc2VzIG9mIHRoaXMgcHJvYmxlbSwgMSBpcyBub3QgcHJpbWUuPFwvcD5cclxuXHJcbjxwPkZvciB0aGlzIHByb2JsZW0geW91IHdpbGwgd3JpdGUgYSBwcm9ncmFtIHRvIGRldGVybWluZSBpZiBhIG51bWJlciBpcyBhIGhhcHB5IHByaW1lLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgYSBzaW5nbGUgaW50ZWdlciBQLCAoMSAmbGU7IFAgJmxlOyAxMDAwKSwgd2hpY2ggaXMgdGhlIG51bWJlciBvZiBkYXRhIHNldHMgdGhhdCBmb2xsb3cuIEVhY2ggZGF0YSBzZXQgc2hvdWxkIGJlIHByb2Nlc3NlZCBpZGVudGljYWxseSBhbmQgaW5kZXBlbmRlbnRseS48XC9wPlxyXG5cclxuPHA+RWFjaCBkYXRhIHNldCBjb25zaXN0cyBvZiBhIHNpbmdsZSBsaW5lIG9mIGlucHV0LiBJdCBjb250YWlucyB0aGUgZGF0YSBzZXQgbnVtYmVyLCBLLCBmb2xsb3dlZCBieSB0aGUgaGFwcHkgcHJpbWUgY2FuZGlkYXRlLCBtLCAoMSAmbGU7IG0gJmxlOyAxMDAwMCkuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggZGF0YSBzZXQgdGhlcmUgaXMgYSBzaW5nbGUgbGluZSBvZiBvdXRwdXQuIFRoZSBzaW5nbGUgb3V0cHV0IGxpbmUgY29uc2lzdHMgb2YgdGhlIGRhdGEgc2V0IG51bWJlciwgSywgZm9sbG93ZWQgYnkgYSBzaW5nbGUgc3BhY2UgZm9sbG93ZWQgYnkgdGhlIGNhbmRpZGF0ZSwgbSwgZm9sbG93ZWQgYnkgYSBzaW5nbGUgc3BhY2UsIGZvbGxvd2VkIGJ5IFlFUyBvciBOTywgaW5kaWNhdGluZyB3aGV0aGVyIG0gaXMgYSBoYXBweSBwcmltZS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d