#1348. 阶乘与最小公倍数

阶乘与最小公倍数

Background

Special for beginners, ^_^

Description

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

Format

Input

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

Output

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

Samples

2
1
2
1
2

Limitation

1s, 1024KiB for each test case.