GOPI_SW - Gopi and Sandwich

no tags 

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<=105) the number of test cases. The next t lines contain one integer per line denoting n(2<=n<=106) 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 109 + 7

Example

Input:
1
3

Output:
6
Explaination:
The possible ways of dividing the sandwich into 3 parts are:
1/3, 1/3, 1/3
1/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 6
1/6, 1/2, 1/3

hide comments
sanjana_17: 2018-08-08 20:35:25

precomputation:)

sanyam19: 2018-01-01 14:43:09

use array to prevent urself from tle.... :)

Baqir khan : 2016-07-22 18:23:38

Lesson learned, never use both cin/cout and scanf/printf in one program !

:?ToRpiDo: 2015-07-20 10:22:37

simple Egyptian Fractions....green:-)

adhikari vushesh babu: 2014-06-08 13:03:53

good question :)

Jumpy: 2014-03-23 18:11:27

really nice one AC in second attempt.
thought it would have been easy to analyze the pattern.

RIVU DAS: 2014-03-14 04:43:47

Thanx @nishant!!

NISHANT RAJ: 2014-03-13 19:03:45

@rivu das : ans for 10^6 = ***
BTW nice problem.

--nitish--> please don't give answers to test cases!

Last edit: 2014-03-15 06:35:13
RIVU DAS: 2014-03-12 18:45:28

@nitish: What is the ans for 10^6???

Sam Winchester: 2014-03-11 20:07:27

Last edit: 2014-05-27 10:13:43

Added by:nitish rao
Date:2014-03-05
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:My own Problem