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

Background

Special for beginners, ^_^

Description

给出正整数n，求最小的正整数k，使得LCM(1, 2, ... n) | k!。

Format

Input

第一行一个正整数T($\le 10^5$)，表示数据组数。 接下来T行，每行一个正整数n($\le 10^9$)。 .

Output

输出T行，每行一个正整数k。.

Samples

2
1
2

1
2

Limitation

1s, 1024KiB for each test case.