Time Limit: 1000MS Memeory Limit:65536KB

Description

在自然数序列中,求去掉所有含2,3,5,7的数字后的第k个数.

Input

第1行为输入组数

第2—T+1行为长度

Output

每组样例输出一行。

 

Sample Input

3

1

4

1000000000000

Sample Output

0

6

4086441010601686