例如，LCM(2)=2,LCM(4,6)=12,LCM(1,2,3,4,5)=60。

现 在给定一个整数N（1<=N<=1000000）,需要找到一个整数M，满足M>N，同时LCM(1,2,3,4,...,N- 1,N) 整除 LCM(N+1,N+2,....,M-1,M)，即LCM(N+1,N+2,....,M-1,M)是LCM(1,2,3,4,...,N-1,N) 的倍数.求最小的M值。

Input

多组测试数据，第一行一个整数T，表示测试数据数量，1<=T<=5

每组测试数据有相同的结构构成：

每组数据一行一个整数N,1<=N<=1000000。

Output

每组数据一行输出，即M的最小值。

Input示例

3

1

2

3

Output示例

2

4

6
保证[1,N]区间每个质数的指数最大值在[N+1,M]间至少出现一次。

 1 #include<iostream>

 2 #include<algorithm>

 3 #include<queue>

 4 #include<set>

 5 #include<math.h>

 6 #include<stdlib.h>

 7 #include<stdio.h>

 8 #include<string.h>

 9 using namespace std;

10 bool prime[1000005];

11 int  ans[100000];

12 int ak[1000005];

13 typedef long long LL;

14 int main(void)

15 {

16         memset(prime,0,sizeof(prime));

17         for(int i = 2; i <= 1000; i++)

18         {

19                 if(!prime[i])

20                 {

21                         for(int j = i; (i*j) <= 1000000 ; j++)

22                         {

23                                 prime[i*j] = true;

24                         }

25                 }

26         }

27         int cn = 0;

28         for(int i = 2; i < 1000000; i++)

29         {

30                 if(!prime[i])

31                         ans[cn++] = i;

32         }

33         int T;

34         scanf("%d",&T);

35         while(T--)

36         {

37                 int n;

38                 scanf("%d",&n);

39                 if(n == 1)printf("2\n");

40                 else if(n==2)printf("4\n");

41                 else if(n==3)printf("6\n");

42                 else

43                 {

44                         fill(ak,ak+1000000,1);

45                         int maxx = 0;

46                         for(int i = 0; i < cn ; i++)

47                         {

48                                 if(ans[i] > n)

49                                 {

50                                         maxx = i-1;

51                                         break;

52                                 }

53                                 int  k = 1;

54                                 int t = 0;

55                                 while(k<=n)

56                                 {

57                                         ak[ans[i]] = max(ak[ans[i]],k) ;

58                                         k*=ans[i];

59                                 }

60                         }if(maxx == 0) maxx = cn;

61                         maxx = min(maxx,cn);

62                         LL x = n;

63                         LL akk = x;

64                         for(int i = 0; i <= maxx; i++)

65                         {

66                                 if(ak[ans[i]]>1)

67                                 {

68                                         LL xx= (x)/ak[ans[i]];

69                                         if(xx*ak[ans[i]] <= x)

70                                         {

71                                                 xx++;

72                                         }

73                                         akk = max(akk,xx*ak[ans[i]]);

74                                 }

75                         }

76                         printf("%lld\n",akk);

77                 }

78         }

79         return 0;

80 }