题目描述

给定一个以$1、3、7$或$9$结尾的十进制数字字符串，总能找到一个十进制数字，该数字的立方的十进制展开以给定的数字字符串结尾。这个数字的位数永远不会超过给定的数字字符串的位数。

编写一个程序，输入一个以$1、3、7$或$9$结尾的十进制数字字符串，并找到一个位数不超过该字符串的数字，使得该数字的立方以给定的数字字符串结尾。

输入格式

• 第一行：一个整数$nProb（1 ≤ nProb ≤ 1000）$，表示问题实例的数量。
• 接下来的$nProb$行：每行包含一个由$1$到$10$个十进制数字组成的字符串，且以$1、3、7$或$9$结尾。

输出格式

• 对于每个问题实例，输出一行，包含一个十进制整数，其立方以给定的数字字符串结尾。输出不应包含前导空格或前导零。

输入样例

4
123
1234567
435621
9876543213

输出样例

947
2835223
786941
2916344917

来源

Greater New York 2005