Arun has a keen interest in maths and recently he came to know about weird function known as Naina function. Arun gave you a number "N" and asked you to evaluate Naina's function. The definition of Naina function is

F ( X ) = X , X <= 9
         = F ( sum of digits in X )
where, X = N³

Input:
First line of input contains T - Total no. of test cases
Each test case contains the number "N".

Output:
For each testcase, print the value of Naina function.

Constraints
1<=T<=100
1<= Number of digits in N <= 10⁴

Problem Setter : Satyam Swarnkar