Background

U510264 ?

Description

若正整数 \(n\) 满足 \(φ(n)\) 为合数，则称其为 \(φ\) 数。其中欧拉函数 \(φ(n)\) 表示在 \(1∼n\) 中与 \(n\) 互质的数的个数

求第 \(k\) 小的 \(φ\) 数 \(n\)

Format

Input

输入数据共 \(T+1\) 行

第一行，输入一个整数 \(T\) ，表示有 \(T\) 组数据

接下去 \(T\) 行，每行输入一个整数 \(k\)，表示要求的是第 \(k\) 小的 \(φ\) 数

Output

对于每组输入数据，输出一个整数表示答案

Sample 1

Input

2
1
2

Output

5
7

Limitation

\(T=10^5 ，1<=k<=10^7\)
50ms for each test case.

Source

zyc Original