Prime Gap Sequence

Interview

Time limit1sMemory limit128 MB

Summary

Given a number k, find the gap length between the two consecutive primes surrounding it if k is composite, otherwise output 0.

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

Problem

For two consecutive primes $p$ and $p + n$ , the $n - 1$ composite numbers strictly between them (a composite number is a positive integer that is neither prime nor 1) form a prime gap sequence of length $n$ .

Given a positive integer $k$ , write a program that determines the length of the prime gap sequence containing $k$ . If no prime gap sequence contains $k$ , its length is 0.

For example, the prime gap sequence between the primes 23 and 29 is $\{24, 25, 26, 27, 28\}$ , and its length is 6.

Input

The first line contains the number of test cases $T$ . Each test case is a single line containing one integer $k$ . Every integer is greater than 1 and at most the 100000th prime, which is 1299709.

Output

For each test case, if $k$ is a composite number, output the length of the prime gap sequence that contains $k$ . Otherwise, output 0.

Examples1

Example 1
Input
```
5
10
11
27
2
492170
```
Expected output
```
4
0
6
0
114
```