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 devises 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 the answer modulo 109 + 7.

Example

Input:
1
3

Output:
6

Explanation:

The possible ways of dividing the sandwich into 3 parts are:

  • 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.


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

hide comments
2021-02-23 08:23:11 majid
If you want to do it with C# or probably JAVA:
Don't write result after each test case. Use StringBuilder and write all the results at once.
2018-08-08 20:35:25
precomputation:)
2018-01-01 14:43:09
use array to prevent urself from tle.... :)
2016-07-22 18:23:38 Baqir khan
Lesson learned, never use both cin/cout and scanf/printf in one program !
2015-07-20 10:22:37 :?ToRpiDo
simple Egyptian Fractions....green:-)
2014-06-08 13:03:53 adhikari vushesh babu
good question :)
2014-03-23 18:11:27 Jumpy
really nice one AC in second attempt.
thought it would have been easy to analyze the pattern.
2014-03-14 04:43:47 RIVU DAS
Thanx @nishant!!
2014-03-13 19:03:45 NISHANT RAJ
@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
2014-03-12 18:45:28 RIVU DAS
@nitish: What is the ans for 10^6???
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.