The Kruzade OPC team felt we should have a happy ending to the Kruzade online coding event. We define the happy sequence as follows: let the sum of the squares of the digits of a positive integer s0 be represented by s1. In a similar way, let the sum of the squares of the digits of s1 be represented by s2, and so on. If si=1 for some i>=1, then the original integer s0 is said to be happy. For example, starting with 7 gives the sequence 7, 49, 97, 130, 10, 1, so 7 is a happy number. The first few happy numbers are 1, 7, 10, 13, 19, 23, 28, 31, 32, 44, 49...

You have been hired to find out the nth happy number in the sequence.

Input

First line contains an integer T, representing the number of test-cases. Then T lines follow each containing one integer n, 1 <= n <= 500.

Output

For each test case output on a line the nth happy number in the sequence.

Example

Input:
3
10
5
20

Output:
44
19
100