B. Different Divisors- Codeforces Round #696 (Div. 2)

Problem - 1474B - Codeforces

B. Different Divisors

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Positive integer xx is called divisor of positive integer yy, if yy is divisible by xx without remainder. For example, 11 is a divisor of 77 and 33 is not divisor of 88.

We gave you an integer dd and asked you to find the smallest positive integer aa, such that

• aa has at least 44 divisors;
• difference between any two divisors of aa is at least dd.

Input

The first line contains a single integer tt (1≤t≤30001≤t≤3000) — the number of test cases.

The first line of each test case contains a single integer dd (1≤d≤100001≤d≤10000).

Output

For each test case print one integer aa — the answer for this test case.

Example

input

Copy

2
1
2

output

Copy

6
15

Note

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

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

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

=========================================================================

抓住4个因子的特殊性，第一个因子为1，一旦我们确定了中间两个因子，那么也就确定了这个数，因为这个数就等于中间两个因子之积，我们想让这个数最小，那么就让中间两个因子最小就够了。

第二个因子必须大于d+1,第三个因子必须大于等于第二个因子+d

如果第二个因子是一个合数，那么势必会有比第二个因子更小的因子出现在前面，所以两者必须是质数，欧拉筛筛出来一定数量的质数，再进行二分查找即可。

# include
# define mod 10
using namespace std;
typedef long long int ll;
 
int prime[1000000+10];
bool not_prime[1000000+10];
int tot;
 
void init()
{
 
    for(int i=2;i<=1000000;i++)
    {
        if(!not_prime[i])
        {
            tot++;
 
            prime[tot]=i;
        }
        for(int j=1;j<=tot&&i*prime[j]<=1000000;j++)
        {
            not_prime[i*prime[j]]=1;
 
           if(i%prime[j]==0)
           {
               break;
           }
 
        }
    }
 
}
int main ()
{
 
   init();
 
   int t;
   cin>>t;
   while(t--)
   {
       int d;
 
       cin>>d;
 
       ll x1=d+1;
 
       int pos=lower_bound(prime+1,prime+1+tot,x1)-prime;
 
       x1=prime[pos];
 
       ll x2=x1+d;
 
        pos=lower_bound(prime+1,prime+1+tot,x2)-prime;
 
       x2=prime[pos];
 
        cout<
 
 
   }
 
 
    return 0;
 
}