Multiple of a Squared Factorial

Time limit3sMemory limit512 MB

Summary

For many queries N, find the smallest K such that K! is divisible by (N!)^2. The answer is always between N and 2N, and needs Legendre exponent checks.

Level: Hard8 of 10
Topics: Number theory, Math, Binary search, Implementation
Solved: No attempts yet

Problem

Given a positive integer $N$ , find the smallest positive integer $K$ such that $K!$ is a multiple of $(N!)^2$ .

An integer $a$ is a multiple of $b$ when $a = b \times k$ holds for some integer $k$ . For a positive integer $M$ , $M!$ is the product of all positive integers that are at most $M$ .

Input

The first line contains $T$ , the number of test cases. Each of the next $T$ lines contains one integer $N$ .

Constraints

$1 \le T \le 200000$
$1 \le N \le 200000$

Output

For each test case, print the answer on its own line.

Examples1

Example 1
Input
```
5
4
5
7
11
24
```
Expected output
```
8
10
14
22
48
```