Array Challenge

Problem Description

Input

The first line of input contains T (1 <= T <= 1000) , the number of test cases. Each test case contains one integer n (1 < n <= $10^{15}$) in one line.

Output

Sample Input

3

4

7

9

Sample Output

1255

324725

13185773

Source

2017 Multi-University Training Contest - Team 10

https://acm.hdu.edu.cn/showproblem.php?pid=6172