Background

Special for beginners, ^_^

Description

输出最小的n位自然数，且其各位数字之和是质数。.

Format

Input

第一行包含一个整数 T (T≤30), 代表测试数据的组数。 接下来T行，每行包含一个整数n (1≤n≤10^6)，表示该数的长度。

Output

共T行每行一个整数，表示该数是多少。

Samples

1
1

2

Limitation

1s, 1024KiB for each test case.