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
2014-03-07 16:34:09 Akhilesh Anandh
Nice problem @nitish rao
2014-03-09 11:25:39 Prasun Joshi
@nitish : where i'm going wrong now?
2014-03-06 20:35:32 Akhil Rao
@nitish
Can you tell me where I'm going wrong? Is my logic correct?
Submission id:11195585

--nitish--> ***

@nitish: Got it !! . Really nice question.Enjoyed solving it :)

Last edit: 2014-03-09 06:22:21
2014-03-06 20:35:32 Bhavik
@nitish: thank you for responding to my queries:)AC
really nice way of framing the question..:)

Last edit: 2014-03-05 18:39:35
2014-03-07 06:31:42 Bhavik
@nitish: thank you for your comment:)
can you kindly tell if i my approach is correct or not? id:11189303

--nitish--> ***

Last edit: 2014-03-09 06:22:38
2014-03-06 20:35:32 knb_dtu
@nitish:Can you pleae provide a test case for which my submission fails?My submission ID :11188142

--nitish--> ***

@nitish:Thanks for responding to my queries.It's really indeed an amazing problem.

Last edit: 2014-03-09 06:22:10
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.