GOPI_SW  Gopi and Sandwich
Gopi is fond of sandwiches. Once his friend asks him to give part of his sandwich. But, Gopi wants to give him as little sandwich as possible. So, he devices a method.
He divides the sandwich into n parts, where each part is a unit fraction( fractions of the form 1/p where p is integer) of the original sandwich. Among all these parts he chooses the smallest part and gives it to his friend. Help Gopi to find the smallest part possible.
Input
First line contains t(1<=t<=10^{5}) the number of test cases. The next t lines contain one integer per line denoting n(2<=n<=10^{6}) the number of parts the sandwich can be divided.
Output
Output one line per test case containing the denominator of the smallest part. Since, the answer can be very large, print Answer modulo 10^{9} + 7
Example
Input: 1
3 Output: 6
Explaination:
The possible ways of dividing the sandwich into 3 parts are:
1/3, 1/3, 1/31/3,1/3,1/3
1/6,1/2,1/3
1/4,1/4,1/2
Among these, the second way has the smallest part. Hence the output is 61/6, 1/2, 1/3
hide comments
sanjana_17:
20180808 20:35:25
precomputation:) 

sanyam19:
20180101 14:43:09
use array to prevent urself from tle.... :) 

Baqir khan :
20160722 18:23:38
Lesson learned, never use both cin/cout and scanf/printf in one program ! 

:?ToRpiDo:
20150720 10:22:37
simple Egyptian Fractions....green:) 

adhikari vushesh babu:
20140608 13:03:53
good question :) 

Jumpy:
20140323 18:11:27
really nice one AC in second attempt.


RIVU DAS:
20140314 04:43:47
Thanx @nishant!! 

NISHANT RAJ:
20140313 19:03:45
@rivu das : ans for 10^6 = ***


RIVU DAS:
20140312 18:45:28
@nitish: What is the ans for 10^6??? 

Sam Winchester:
20140311 20:07:27
Last edit: 20140527 10:13:43 
Added by:  nitish rao 
Date:  20140305 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 
Resource:  My own Problem 