시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 41 18 15 44.118%

문제

1, 3, 7, 9로 끝나는 숫자 S가 주어진다. 이 때, 세제곱했을 때, S로 끝나는 수가 반드시 존재한다.

예를들어, S가 123이면, 947을 세제곱하면 849278123이 되고, 이 수는 123으로 끝난다.

S가 주어졌을 때, 세제곱했을 때 S로 끝나는 숫자를 찾아 출력하는 프로그램을 작성하시오. 이때 x의 길이는 S의 길이보다 작거나 같아야 한다.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 둘째줄 부터 T개 줄에는 테스트 케이스의 정보가 주어진다. 각 테스트 케이스는 숫자 하나로 이루어져 있고, 이 수는 문제에서 설명한 S이다. S는 1, 3, 7, 9로 끝나며, 최대 10자리이다.

출력

각 테스트 케이스에 대해 한 줄에 하나씩 세제곱햇을 때 S가 되는 수 x를 출력한다.

예제 입력 1

4
123
1234567
435621
9876543213

예제 출력 1

947
2835223
786941
2916344917
W3sicHJvYmxlbV9pZCI6IjI3MzEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiIxMzc5XHVjNjQwIFx1YzEzOFx1YzgxY1x1YWNmMSIsImRlc2NyaXB0aW9uIjoiPHA+XHJcblx0MSwgMywgNywgOVx1Yjg1YyBcdWIwNWRcdWIwOThcdWIyOTQgXHVjMjJiXHVjNzkwIFNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3NzQgXHViNTRjLCBcdWMxMzhcdWM4MWNcdWFjZjFcdWQ1ODhcdWM3NDQgXHViNTRjLCBTXHViODVjIFx1YjA1ZFx1YjA5OFx1YjI5NCBcdWMyMThcdWFjMDAgXHViYzE4XHViNGRjXHVjMmRjIFx1Yzg3NFx1YzdhY1x1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHVjNjA4XHViOTdjXHViNGU0XHVjNWI0LCBTXHVhYzAwIDEyM1x1Yzc3NFx1YmE3NCwgOTQ3XHVjNzQ0IFx1YzEzOFx1YzgxY1x1YWNmMVx1ZDU1OFx1YmE3NCA4NDkyNzgxMjNcdWM3NzQgXHViNDE4XHVhY2UwLCBcdWM3NzQgXHVjMjE4XHViMjk0IDEyM1x1YzczY1x1Yjg1YyBcdWIwNWRcdWIwOWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVjMTM4XHVjODFjXHVhY2YxXHVkNTg4XHVjNzQ0IFx1YjU0YyBTXHViODVjIFx1YjA1ZFx1YjA5OFx1YjI5NCBcdWMyMmJcdWM3OTBcdWI5N2MgXHVjYzNlXHVjNTQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LiBcdWM3NzRcdWI1NGMgeFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWIyOTQgU1x1Yzc1OCBcdWFlMzhcdWM3NzRcdWJjZjRcdWIyZTQgXHVjNzkxXHVhYzcwXHViMDk4IFx1YWMxOVx1YzU0NFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cclxuXHRcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVhYzFjXHVjMjE4IFRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWI0NThcdWM5ZjhcdWM5MDQgXHViZDgwXHVkMTMwIFRcdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjODE1XHViY2Y0XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWIyOTQgXHVjMjJiXHVjNzkwIFx1ZDU1OFx1YjA5OFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHVhY2UwLCBcdWM3NzQgXHVjMjE4XHViMjk0IFx1YmIzOFx1YzgxY1x1YzVkMFx1YzExYyBcdWMxMjRcdWJhODVcdWQ1NWMgU1x1Yzc3NFx1YjJlNC4gU1x1YjI5NCAxLCAzLCA3LCA5XHViODVjIFx1YjA1ZFx1YjA5OFx1YmE3MCwgXHVjZDVjXHViMzAwIDEwXHVjNzkwXHViOWFjXHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlxyXG5cdFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NCBcdWQ1NWMgXHVjOTA0XHVjNWQwIFx1ZDU1OFx1YjA5OFx1YzUyOSBcdWMxMzhcdWM4MWNcdWFjZjFcdWQ1ODdcdWM3NDQgXHViNTRjIFNcdWFjMDAgXHViNDE4XHViMjk0IFx1YzIxOCB4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIyNzMxIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiVGhlIEN1YmljIEVuZCIsImRlc2NyaXB0aW9uIjoiPHA+R2l2ZW4gYW55IHN0cmluZyBvZiBkZWNpbWFsIGRpZ2l0cywgZW5kaW5nIGluIDEsIDMsIDcgb3IgOSwgdGhlcmUgaXMgYWx3YXlzIGEgZGVjaW1hbCBudW1iZXIsIHdoaWNoIHdoZW4gY3ViZWQgaGFzIGEgZGVjaW1hbCBleHBhbnNpb24gZW5kaW5nIGluIHRoZSBvcmlnaW5hbCBnaXZlbiBkaWdpdCBzdHJpbmcuIFRoZSBudW1iZXIgbmVlZCBuZXZlciBoYXZlIG1vcmUgZGlnaXRzIHRoYW4gdGhlIGdpdmVuIGRpZ2l0IHN0cmluZy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtLCB3aGljaCB0YWtlcyBhcyBpbnB1dCBhIHN0cmluZyBvZiBkZWNpbWFsIGRpZ2l0cyBlbmRpbmcgaW4gMSwgMywgNyBvciA5IGFuZCBmaW5kcyBhIG51bWJlciBvZiBhdCBtb3N0IHRoZSBzYW1lIG51bWJlciBvZiBkaWdpdHMsIHdoaWNoIHdoZW4gY3ViZWQsIGVuZHMgaW4gdGhlIGdpdmVuIGRpZ2l0IHN0cmluZy4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBpbnB1dCBiZWdpbnMgd2l0aCBhIGxpbmUgY29udGFpbmluZyBvbmx5IHRoZSBjb3VudCBvZiBwcm9ibGVtIGluc3RhbmNlcywgblByb2IsIGFzIGEgZGVjaW1hbCBpbnRlZ2VyLCAxICZsdDs9IG5Qcm9iICZsdDs9IDEwMDAuIFRoaXMgaXMgZm9sbG93ZWQgYnkgblByb2IgbGluZXMsIGVhY2ggb2Ygd2hpY2ggY29udGFpbnMgYSBzdHJpbmcgb2YgYmV0d2VlbiAxIGFuZCAxMCBkZWNpbWFsIGRpZ2l0cyBlbmRpbmcgaW4gMSwgMywgNyBvciA5LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHByb2JsZW0gaW5zdGFuY2UsIHRoZXJlIHNob3VsZCBiZSBvbmUgbGluZSBvZiBvdXRwdXQgY29uc2lzdGluZyBvZiB0aGUgbnVtYmVyLCB3aGljaCB3aGVuIGN1YmVkLCBlbmRzIGluIHRoZSBnaXZlbiBkaWdpdCBzdHJpbmcuIFRoZSBudW1iZXIgc2hvdWxkIGJlIG91dHB1dCBhcyBhIGRlY2ltYWwgaW50ZWdlciB3aXRoIG5vIGxlYWRpbmcgc3BhY2VzIGFuZCBubyBsZWFkaW5nIHplcm9lcy4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=