Different Divisors
Contest: Codeforces Round 696 (Div. 2)
Difficulty rating: 1000
Tags: binary search, constructive algorithms, greedy, math, number theory

Positive integer $$$x$$$ is called divisor of positive integer $$$y$$$, if $$$y$$$ is divisible by $$$x$$$ without remainder. For example, $$$1$$$ is a divisor of $$$7$$$ and $$$3$$$ is not divisor of $$$8$$$.

We gave you an integer $$$d$$$ and asked you to find the smallest positive integer $$$a$$$, such that

- $$$a$$$ has at least $$$4$$$ divisors;
- difference between any two divisors of $$$a$$$ is at least $$$d$$$.

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 3000$$$) — the number of test cases.

The first line of each test case contains a single integer $$$d$$$ ($$$1 \leq d \leq 10000$$$).

Output format:
For each test case print one integer $$$a$$$ — the answer for this test case.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first test case, integer $$$6$$$ have following divisors: $$$[1, 2, 3, 6]$$$. There are $$$4$$$ of them and the difference between any two of them is at least $$$1$$$. There is no smaller integer with at least $$$4$$$ divisors.

In the second test case, integer $$$15$$$ have following divisors: $$$[1, 3, 5, 15]$$$. There are $$$4$$$ of them and the difference between any two of them is at least $$$2$$$.

The answer $$$12$$$ is INVALID because divisors are $$$[1, 2, 3, 4, 6, 12]$$$. And the difference between, for example, divisors $$$2$$$ and $$$3$$$ is less than $$$d=2$$$.

Example input:
2
1
2

Example output:
6
15

Editorial:
Hint $$$1$$$: Integer have exactly $$$4$$$ divisors, if it is of form $$$pq$$$ or $$$p^3$$$ for some primes $$$p$$$ and $$$q$$$. In the first case it have divisors $$$1$$$, $$$p$$$, $$$q$$$, $$$pq$$$. In the second case it have divisors $$$1$$$, $$$p$$$, $$$p^2$$$, $$$p^3$$$.
Hint $$$2$$$: Instead of finding integer with at least $$$4$$$ divisors, find integer with exactly $$$4$$$ divisors.
Hint $$$3$$$: Let $$$p$$$ be the smallest prime factor of $$$a$$$. Then, $$$p \geq d + 1$$$.
Solution:
Suppose, we have integer $$$a$$$ with more than $$$4$$$ divisors (and satisfies the other condition). If $$$a$$$ has at least two different prime factors, we can throw out all other prime factors and get a smaller number with at least $$$4$$$ divisors. Otherwise, $$$a = p^k$$$ for some $$$k > 3$$$. $$$p^3$$$ will also have $$$4$$$ divisors and it will be smaller than $$$a$$$. When we throw out a prime factor, no new divisors will appear, so the difference between any two of them will be at least $$$d$$$.
Let's find smallest integers of form $$$p^3$$$ and $$$pq$$$ $$$(p<q)$$$ independently.
In the first case, $$$p^3 - p^2 > p^2 - p > p - 1$$$, because $$$p \geq 2$$$. If we will find the smallest $$$p \geq d + 1$$$ all conditions will be satisfied.
In the second case, $$$1 < p < q < pq$$$. Let's find the smallest $$$p \geq d + 1$$$ and the smallest $$$q \geq d + p$$$. In this case it is easy to see that $$$p - 1 \geq d$$$ and $$$q - p \geq d$$$. Also, $$$pq - q = q(p - 1) \geq qd \geq d$$$ since $$$q \geq 2$$$. It is enough to get OK even without checking case $$$a = p^3$$$.
Also we should prove that there cannot exist $$$p'$$$ and $$$q'$$$ such that $$$p'q' < pq$$$. It is true because $$$p'$$$ should be at least $$$d+1$$$ and it should be prime, but $$$p$$$ is the smallest prime greater than $$$d$$$, so $$$p' \geq p$$$. And $$$q'$$$ should be at least $$$p+d$$$ and we can prove that $$$q' \geq q$$$ in the same way.
Time complexity is $$$\mathcal{O}(t \cdot \mathit{gap} \cdot \mathit{primecheck})$$$, where $$$\mathit{gap}$$$ is difference between primes and $$$\mathcal{O}(\log{a})$$$ in average and $$$primecheck$$$ is complexity of your prime check and usually is $$$\mathcal{O}(\sqrt{a})$$$.
Answer for $$$d = 10000$$$ is near to $$$2 \cdot 10^8$$$, so naive solution with factorization of each number shouldn't pass, but it is possible to precompute answers for all values of $$$d$$$ by that solution (in this case, you should run solution once for all values of $$$d$$$, not once for each value of $$$d$$$).