问题描述

存在这样的一个序列，我们称之为半素数序列。该序列的前几项为 $4, 6, 9, 10, 14, \ldots$。在半素数序列中，每一项都是由两个素数相乘得到，并按照从小到大的顺序排列。

现在给定 $q$ 组查询，每组查询包含一个正整数 $n$，你需要输出半素数序列的第 $n$ 项的值。

输入格式

第一行输入一个正整数 $q$，表示查询的数量。

接下来 $q$ 行，每行输入一个正整数 $n$，表示一个查询。

输出格式

输出 $q$ 行，每行包含一个正整数，表示对应查询的结果。

样例输入

3
3
6
278

样例输出

9
15
923

评测数据规模

$1\le q\le 10^5,1\le n \le 2\times 10^5$。