시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB57626119943.736%

문제

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+MSwgMywgNywgOVx1Yjg1YyBcdWIwNWRcdWIwOThcdWIyOTQgXHVjMjJiXHVjNzkwIFNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3NzRcdWI1NGMsIFx1YzEzOFx1YzgxY1x1YWNmMVx1ZDU4OFx1Yzc0NCBcdWI1NGMsIFNcdWI4NWMgXHViMDVkXHViMDk4XHViMjk0IFx1YzIxOFx1YWMwMCBcdWJjMThcdWI0ZGNcdWMyZGMgXHVjODc0XHVjN2FjXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM2MDhcdWI5N2NcdWI0ZTRcdWM1YjQsIFNcdWFjMDAgMTIzXHVjNzc0XHViYTc0LCA5NDdcdWM3NDQgXHVjMTM4XHVjODFjXHVhY2YxXHVkNTU4XHViYTc0IDg0OTI3ODEyM1x1Yzc3NCBcdWI0MThcdWFjZTAsIFx1Yzc3NCBcdWMyMThcdWIyOTQgMTIzXHVjNzNjXHViODVjIFx1YjA1ZFx1YjA5Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+U1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWMxMzhcdWM4MWNcdWFjZjFcdWQ1ODhcdWM3NDQgXHViNTRjIFNcdWI4NWMgXHViMDVkXHViMDk4XHViMjk0IFx1YzIyYlx1Yzc5MFx1Yjk3YyBcdWNjM2VcdWM1NDQgXHVjZDljXHViODI1XHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuIFx1Yzc3NFx1YjU0YyB4XHVjNzU4IFx1YWUzOFx1Yzc3NFx1YjI5NCBTXHVjNzU4IFx1YWUzOFx1Yzc3NFx1YmNmNFx1YjJlNCBcdWM3OTFcdWFjNzBcdWIwOTggXHVhYzE5XHVjNTQ0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWFjMWNcdWMyMTggVFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjQ1OFx1YzlmOCBcdWM5MDQgXHViZDgwXHVkMTMwIFRcdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjODE1XHViY2Y0XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWIyOTQgXHVjMjJiXHVjNzkwIFx1ZDU1OFx1YjA5OFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHVhY2UwLCBcdWM3NzQgXHVjMjE4XHViMjk0IFx1YmIzOFx1YzgxY1x1YzVkMFx1YzExYyBcdWMxMjRcdWJhODVcdWQ1NWMgU1x1Yzc3NFx1YjJlNC4gU1x1YjI5NCAxLCAzLCA3LCA5XHViODVjIFx1YjA1ZFx1YjA5OFx1YmE3MCwgXHVjZDVjXHViMzAwIDEwXHVjNzkwXHViOWFjXHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NCBcdWQ1NWMgXHVjOTA0XHVjNWQwIFx1ZDU1OFx1YjA5OFx1YzUyOSBcdWMxMzhcdWM4MWNcdWFjZjFcdWQ1ODhcdWM3NDQgXHViNTRjIFNcdWFjMDAgXHViNDE4XHViMjk0IFx1YzIxOCB4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIyNzMxIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiVGhlIEN1YmljIEVuZCIsImRlc2NyaXB0aW9uIjoiPHA+R2l2ZW4gYW55IHN0cmluZyBvZiBkZWNpbWFsIGRpZ2l0cywgZW5kaW5nIGluIDEsIDMsIDcgb3IgOSwgdGhlcmUgaXMgYWx3YXlzIGEgZGVjaW1hbCBudW1iZXIsIHdoaWNoIHdoZW4gY3ViZWQgaGFzIGEgZGVjaW1hbCBleHBhbnNpb24gZW5kaW5nIGluIHRoZSBvcmlnaW5hbCBnaXZlbiBkaWdpdCBzdHJpbmcuIFRoZSBudW1iZXIgbmVlZCBuZXZlciBoYXZlIG1vcmUgZGlnaXRzIHRoYW4gdGhlIGdpdmVuIGRpZ2l0IHN0cmluZy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtLCB3aGljaCB0YWtlcyBhcyBpbnB1dCBhIHN0cmluZyBvZiBkZWNpbWFsIGRpZ2l0cyBlbmRpbmcgaW4gMSwgMywgNyBvciA5IGFuZCBmaW5kcyBhIG51bWJlciBvZiBhdCBtb3N0IHRoZSBzYW1lIG51bWJlciBvZiBkaWdpdHMsIHdoaWNoIHdoZW4gY3ViZWQsIGVuZHMgaW4gdGhlIGdpdmVuIGRpZ2l0IHN0cmluZy4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBpbnB1dCBiZWdpbnMgd2l0aCBhIGxpbmUgY29udGFpbmluZyBvbmx5IHRoZSBjb3VudCBvZiBwcm9ibGVtIGluc3RhbmNlcywgblByb2IsIGFzIGEgZGVjaW1hbCBpbnRlZ2VyLCAxICZsdDs9IG5Qcm9iICZsdDs9IDEwMDAuIFRoaXMgaXMgZm9sbG93ZWQgYnkgblByb2IgbGluZXMsIGVhY2ggb2Ygd2hpY2ggY29udGFpbnMgYSBzdHJpbmcgb2YgYmV0d2VlbiAxIGFuZCAxMCBkZWNpbWFsIGRpZ2l0cyBlbmRpbmcgaW4gMSwgMywgNyBvciA5LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHByb2JsZW0gaW5zdGFuY2UsIHRoZXJlIHNob3VsZCBiZSBvbmUgbGluZSBvZiBvdXRwdXQgY29uc2lzdGluZyBvZiB0aGUgbnVtYmVyLCB3aGljaCB3aGVuIGN1YmVkLCBlbmRzIGluIHRoZSBnaXZlbiBkaWdpdCBzdHJpbmcuIFRoZSBudW1iZXIgc2hvdWxkIGJlIG91dHB1dCBhcyBhIGRlY2ltYWwgaW50ZWdlciB3aXRoIG5vIGxlYWRpbmcgc3BhY2VzIGFuZCBubyBsZWFkaW5nIHplcm9lcy4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d