#OJ2264. 光棍lwc

光棍lwc

光棍lwc

Time Limit: 1 Sec  Memory Limit: 128 MB

Description

寂寞的11.11光棍节到了,可怜的大光棍lwc还是没有女朋友,面对身旁走过的一对对情侣,他终于忍不住了,他大声喊道:“一股凉风一阵寒,一片落叶一场秋;一年一度光棍节,一人举杯邀明月;一眼望去一对对,一点一滴心底起;一个愿望突激起,一人不再过此节!”他渴望在今年光棍节找到一个对象,但是他不是一个随便的男人,他考虑了一下,决定提出一个问题,谁能第一个AC谁就做他的对象! 题目如下: lwc看到连11.11都是成对的,心里很不爽,所以他决定拆散他们。他想找到一个数,使得它的三次方的后三位是111。经过他不懈的努力,从0开始寻找,终于找到了这样的第一个数471,471的三次方是104487111。找到这第一个数就把他累坏了,但是他还想继续找下去,所以请求你的帮助,你能帮他找到第m个这样的数吗?

Input

第一行一个 T 表示接下来有T组输入 接下来T行,每行一个整数m(1<=m<=100000000000)

Output

T行,每行一个数n,表示找到的第m个满足条件的数

Sample Input

1
1

Sample Output

471

HINT