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

문제

어떤 수를 왼쪽부터 읽어도, 오른쪽부터 읽어도 같을 때 이 수를 회문인 수라고 한다. 예를 들어, 747은 회문인 수이다. 255도 회문인 수인데, 16진수로 표현하면 FF이기 때문이다. 양의 정수를 입력받았을 때, 이 수가 어떤 B진법 (2 ≤ B ≤ 64)으로 표현하면 회문이 되는 경우가 있는지 알려주는 프로그램을 작성하시오. B진법이란, 한 자리에서 수를 표현할 때 쓸 수 있는 수의 가짓수가 B라는 뜻이다. 예를 들어, 십진법에서 B는 10이다. 

입력

입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 테스트 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터는 64 이상 1,000,000 이하인 하나의 정수로 주어진다.

출력

출력은 표준출력을 사용한다. 하나의 테스트 데이터에 대한 답을 하나의 줄에 출력한다. 각 테스트 데이터에 대해, 주어진 수가 어떤 B진법 (2 ≤ B ≤ 64)으로 표현하여 회문이 될 수 있다면 1을, 그렇지 않다면 0을 출력한다.

예제 입력 1

3
747
255
946734

예제 출력 1

1
1
0
W3sicHJvYmxlbV9pZCI6IjExMDY4IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVkNjhjXHViYjM4XHVjNzc4IFx1YzIxOCIsImRlc2NyaXB0aW9uIjoiPHA+XHVjNWI0XHViNWE0IFx1YzIxOFx1Yjk3YyBcdWM2N2NcdWNhYmRcdWJkODBcdWQxMzAgXHVjNzdkXHVjNWI0XHViM2M0LCBcdWM2MjRcdWI5NzhcdWNhYmRcdWJkODBcdWQxMzAgXHVjNzdkXHVjNWI0XHViM2M0IFx1YWMxOVx1Yzc0NCBcdWI1NGMgXHVjNzc0IFx1YzIxOFx1Yjk3YyBcdWQ2OGNcdWJiMzhcdWM3NzggXHVjMjE4XHViNzdjXHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgNzQ3XHVjNzQwIFx1ZDY4Y1x1YmIzOFx1Yzc3OCBcdWMyMThcdWM3NzRcdWIyZTQuIDI1NVx1YjNjNCBcdWQ2OGNcdWJiMzhcdWM3NzggXHVjMjE4XHVjNzc4XHViMzcwLCAxNlx1YzljNFx1YzIxOFx1Yjg1YyBcdWQ0NWNcdWQ2MDRcdWQ1NThcdWJhNzQgRkZcdWM3NzRcdWFlMzAgXHViNTRjXHViYjM4XHVjNzc0XHViMmU0LiBcdWM1OTFcdWM3NTggXHVjODE1XHVjMjE4XHViOTdjIFx1Yzc4NVx1YjgyNVx1YmMxYlx1YzU1OFx1Yzc0NCBcdWI1NGMsIFx1Yzc3NCBcdWMyMThcdWFjMDAgXHVjNWI0XHViNWE0IEJcdWM5YzRcdWJjOTUgKDIgJmxlOyBCICZsZTsgNjQpXHVjNzNjXHViODVjIFx1ZDQ1Y1x1ZDYwNFx1ZDU1OFx1YmE3NCBcdWQ2OGNcdWJiMzhcdWM3NzQgXHViNDE4XHViMjk0IFx1YWNiZFx1YzZiMFx1YWMwMCBcdWM3ODhcdWIyOTRcdWM5YzAgXHVjNTRjXHViODI0XHVjOGZjXHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuIEJcdWM5YzRcdWJjOTVcdWM3NzRcdWI3ODAsIFx1ZDU1YyBcdWM3OTBcdWI5YWNcdWM1ZDBcdWMxMWMgXHVjMjE4XHViOTdjIFx1ZDQ1Y1x1ZDYwNFx1ZDU2MCBcdWI1NGMgXHVjNGY4IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjMjE4XHVjNzU4IFx1YWMwMFx1YzlkM1x1YzIxOFx1YWMwMCBCXHViNzdjXHViMjk0IFx1YjczYlx1Yzc3NFx1YjJlNC4gXHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgXHVjMmVkXHVjOWM0XHViYzk1XHVjNWQwXHVjMTFjIEJcdWIyOTQgMTBcdWM3NzRcdWIyZTQuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWM3ODVcdWI4MjUgXHViMzcwXHVjNzc0XHVkMTMwXHViMjk0IFx1ZDQ1Y1x1YzkwMFx1Yzc4NVx1YjgyNVx1Yzc0NCBcdWMwYWNcdWM2YTlcdWQ1NWNcdWIyZTQuIFx1Yzc4NVx1YjgyNVx1Yzc0MCBUXHVhYzFjXHVjNzU4IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWIzNzBcdWM3NzRcdWQxMzBcdWI4NWMgXHVhZDZjXHVjMTMxXHViNDFjXHViMmU0LiBcdWM3ODVcdWI4MjVcdWM3NTggXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVkMTRjXHVjMmE0XHVkMmI4IFx1YjM3MFx1Yzc3NFx1ZDEzMFx1Yzc1OCBcdWMyMThcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IFx1YzgxNVx1YzIxOCBUXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWIzNzBcdWM3NzRcdWQxMzBcdWIyOTQgNjQgXHVjNzc0XHVjMGMxIDEsMDAwLDAwMCBcdWM3NzRcdWQ1NThcdWM3NzggXHVkNTU4XHViMDk4XHVjNzU4IFx1YzgxNVx1YzIxOFx1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjZDljXHViODI1XHVjNzQwIFx1ZDQ1Y1x1YzkwMFx1Y2Q5Y1x1YjgyNVx1Yzc0NCBcdWMwYWNcdWM2YTlcdWQ1NWNcdWIyZTQuIFx1ZDU1OFx1YjA5OFx1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHViMzcwXHVjNzc0XHVkMTMwXHVjNWQwIFx1YjMwMFx1ZDU1YyBcdWIyZjVcdWM3NDQgXHVkNTU4XHViMDk4XHVjNzU4IFx1YzkwNFx1YzVkMCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHViMzcwXHVjNzc0XHVkMTMwXHVjNWQwIFx1YjMwMFx1ZDU3NCwgXHVjOGZjXHVjNWI0XHVjOWM0IFx1YzIxOFx1YWMwMCBcdWM1YjRcdWI1YTQgQlx1YzljNFx1YmM5NSAoMiAmbGU7IEIgJmxlOyA2NClcdWM3M2NcdWI4NWMgXHVkNDVjXHVkNjA0XHVkNTU4XHVjNWVjIFx1ZDY4Y1x1YmIzOFx1Yzc3NCBcdWI0MjAgXHVjMjE4IFx1Yzc4OFx1YjJlNFx1YmE3NCAxXHVjNzQ0LCBcdWFkZjhcdWI4MDdcdWM5YzAgXHVjNTRhXHViMmU0XHViYTc0IDBcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjExMDY4IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiUGFsaW5kcm9taWMgTnVtYmVycyIsImRlc2NyaXB0aW9uIjoiPHA+QSBudW1iZXIgaXMgYSBwYWxpbmRyb21lIGlmIGl0IHJlYWRzIHRoZSBzYW1lIGJhY2t3YXJkIG9yIGZvcndhcmQuIEZvciBleGFtcGxlLCA3NDcgaXMgYSBwYWxpbmRyb21lLiAyNTUgaXMgYWxzbyBhIHBhbGluZHJvbWUgYXMgaXQgaXMgRkYgaW4gaGV4YWRlY2ltYWwuIEdpdmVuIGEgcG9zaXRpdmUgaW50ZWdlciwgd3JpdGUgYSBwcm9ncmFtIHdoZXRoZXIgaXQgY2FuIGJlIGEgcGFsaW5kcm9tZSB3aXRoIGEgY2VydGFpbiBiYXNlIEIgKDIgJmxlOyBCICZsZTsgNjQpLiBOb3RlIHRoYXQgdGhlIGJhc2UgaXMgdGhlIG51bWJlciBvZiB1bmlxdWUgZGlnaXRzIChpbmNsdWRpbmcgemVybykgdXNlZCB0byByZXByZXNlbnQgbnVtYmVycy4gRm9yIGV4YW1wbGUsIGZvciB0aGUgZGVjaW1hbCBzeXN0ZW0gdGhlIGJhc2UgQiBpcyAxMC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPllvdXIgcHJvZ3JhbSBpcyB0byByZWFkIGZyb20gc3RhbmRhcmQgaW5wdXQuIFRoZSBpbnB1dCBjb25zaXN0cyBvZiBUIHRlc3QgY2FzZXMuIFRoZSBudW1iZXIgb2YgdGVzdCBjYXNlcyBUIGlzIGdpdmVuIGluIHRoZSBmaXJzdCBsaW5lIG9mIHRoZSBpbnB1dC4gRWFjaCB0ZXN0IGNhc2UgY29uc2lzdHMgb2YgYSBsaW5lIGNvbnRhaW5pbmcgYSBwb3NpdGl2ZSBpbnRlZ2VyIGJldHdlZW4gNjQgYW5kIDEsMDAwLDAwMCwgaW5jbHVzaXZlbHkuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+WW91ciBwcm9ncmFtIGlzIHRvIHdyaXRlIHRvIHN0YW5kYXJkIG91dHB1dC4gUHJpbnQgZXhhY3RseSBvbmUgbGluZSBmb3IgZWFjaCB0ZXN0IGNhc2UuIFRoZSBsaW5lIHNob3VsZCBjb250YWluIDEgaWYgdGhlIG51bWJlciBjYW4gYmUgYSBwYWxpbmRyb21lIHdpdGggYSBjZXJ0YWluIGJhc2UgQiAoMiAmbGU7IEIgJmxlOyA2NCksIGFuZCAwIG90aGVyd2lzZS4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d