SMALL - Smallest Number


Your task is extremely simple, for a given number N you have to find the smallest number which is divisible by all numbers from 1 to N without leaving any remainder. As the number can be very large print the answer modulo 1000000007.

Input

Input starts with a positive integer T < 501 in a single line, then T lines follow. Each of the T lines contains one positive integer N < 10001.

Output

For every N print the desired number.

Example

Input:
1
5

Output:
60

hide comments
DHEERAJ KUMAR: 2015-07-06 22:54:59

finally removed this problem from TODO list after 1 month :)
difficult to do it with c++ :)

bhavik_: 2015-06-29 19:30:49

python Rocckksssss . . . .

kp: 2015-06-29 13:49:17

getting nzec in both java and python , ac with cpp

--(Lakshman)--> did you see what is the difference between your python and C++ code.
--(kp) --> got it! thanks

Last edit: 2015-06-30 06:34:00
:.Mohib.:: 2015-06-18 06:54:30

Nice que!!

coder: 2015-06-04 11:02:06

getting WA again and again. Though algo seems to be fine @Lakshman plz check.

Nitesh Tiwari: 2015-06-02 00:09:39

Is lcm of 1000 = 98552301000?

Last edit: 2015-06-07 21:11:58
Akshat Mathur: 2015-05-30 12:49:37

AC in one go !!

Maroof: 2015-05-23 18:04:56

@Ayushi in your def pow function, there should be a "<=" condition instead of "<"

Last edit: 2015-05-23 18:43:47
Joaquin: 2015-04-26 17:24:51

@_R0b_ hi, thanks for the answer, i know the complexity of my algo(n+(n^2)/2) and i know the solution with the sieve.My points is if 1 case passes the test, all the test have the same complexity , cuz i use the preprocess.I really dont understand why give me TLE :(.

_R0b_: 2015-04-26 10:36:51

@Joaquin / for your solution the time complexity is

for 1st for loop is 10001
for 2nd for loop is 10001
and for 3rd for loop is 10001 * 10001
so total complexity of your program is ( O( n + n^2 ) may be and) its definitely gives you TLE :)

I think before that problem you should try the easy one - > go to hackerrank.com -> contest -> project Euler -> solve "Smallest Multiplies " i don't remember the Problem no may be its between 12 to 20 -> first go for it

Last edit: 2015-04-26 10:48:52

Added by:[Lakshman]
Date:2015-01-24
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 JS-MONKEY