该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

yq次次都是最难的那道题的主角，所以这次也是（笑）。咩咩上场比赛打的不是很理想，所以有些失落，yq为了安慰他，选择一起吃晚饭，在餐桌上，yq为了鼓励咩咩训练思维，跟他一起玩报数游戏，想让咩咩从生活中获得动力。不知道大家知不知道逢七过这个游戏，如果下一个报的数是7的倍数，或者数里含有七时，这个数必须被跳过，否则就输了，不过yq加强了这个游戏，如果一个数含七，那么他的所有倍数都不能报例如，如果yq报出了 6 ，由于 7 不能报，所以咩咩下一个需要报 8；如果yq 报出了 33，则由于 $34 = 17 \times 2$（17含有7且34是17的倍数），$35 = 7 \times 5$ 都不能报，咩咩下一个需要报出 36 ；如果yq报出了 69，由于 $70 \sim 79$ 的数都含有 7，咩咩下一个需要报出 80 才行。现在yq的上一个数报出了 x，咩咩想快速算出他下一个数要报多少，不过他需要你的帮助（呜呜呜，救救孩子）。当然，如果yq报出的 x 本身是不能报出的，你也要快速反应过来yq输了才行。

Input

第一行，一个正整数 T 表示yq报数的数量。

接下来 T 行，每行一个正整数 x，表示这一次yq报出的数。 对于 100% 的数据，$1 \le T \leq 2 \times {10}^5$，$1 \le x \leq {10}^7$。

Output

输出共 T 行，每行一个整数，如果yq 这一次报出的数是不能报出的，输出 -1，否则输出咩咩下一次报出的数是多少。

Samples

4
6
33
69
300

8
36
80
-1

提示

对于第 4 次询问，由于 $300 = 75 \times 4$，而 75 中含有 7 ，所以yq直接输掉了游戏。