NUMTRY - Number Theory

f(n) and g(n) are two functions defined as following :

f(n) = ( pi2ei+1+1 ), where pi is prime factor of n and ei is highest power of pi in n.

g(n) = Σ( n/gcd(n,i) ); 1 <= i  <= n

For a given value of n, you have to compute [f(n)/g(n)] % 1000000007.

Input

First line has T ( <= 10000 ), next T lines has 2 <= n <= 10^12.

Output

[f(n)/g(n)] % 1000000007 for each test case.

Example

Input:
2
2
4 Output:
3
3

Warning: Test cases aren't random. Test files consist of large primes, strong pseudo primes, Carmichael numbers, squares of primes, product of large primes, worst possible test cases for fermat, miller rabin and other primality testing algorithms.

Note: You may try the tutorial version ( same test files, 5s-100s time limit ). 


Added by:XeRoN!X
Date:2012-03-23
Time limit:0.100s-1.192s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Number Theory

hide comments
2014-12-31 19:55:28 Yashpal
Awesome Problem !! Reduced in Simple formula ! :)

Last edit: 2014-12-31 20:16:47
2014-06-22 15:29:09 Viplov Jain
@xeronix please provide information on test files like given on this page ->http://www.spoj.com/problems/APS2/
my total time is lower than some AC solutions

finally did it. but still... the information on test files would be quite helpful for the solvers

Last edit: 2014-06-23 17:51:31
2014-06-07 13:47:00 [Lakshman]
Finally accepted took three moths to solve this problem.
(Re:xeronix) : Great :)

Last edit: 2014-06-07 13:44:40
2014-06-07 13:47:00 [Lakshman]
@XeRo!NiX My new Solution seems faster than 2 accepted users in easy version but here TLE, Do the easy version have different input files?

(Re:Author) : Both versions have same test files. Your TLE solution was faster in overall time but slower than the limit in some of the test files.

Last edit: 2014-06-07 13:37:08
2014-06-07 13:47:00 [Lakshman]
@XeRo!NiX can you please suggest me some optimistion

Last edit: 2014-02-25 08:36:21
2014-06-07 13:47:00 apia
It seems my total time is faster than Damian Straszak,but I got TLE again.
Re( Author ): Yes but in couple of test files your solution is slower and crosses the limit.
Thx,it's a really tricky case.My program runs much faster when I notice this.BTW,it took me nearly a year to solve this problem...

Last edit: 2013-03-14 07:37:41
2014-06-07 13:47:00 teoy
the time limit is for one case or all cases ?
2014-06-07 13:47:00 Damian Straszak
the tutorial version is very helpful, thank you
2014-06-07 13:47:00 Damian Straszak
Ok, so this is tough. I Have no idea how to speed up my code. Any hints :)?
2014-06-07 13:47:00 Damian Straszak
It's pretty hard to factorize n, when the time limit is so strict... (btw. why not equal limits for all testcases?).

Re ( Author ) : Number of test cases and their nature is different in different test files. So unequal time limits.

Last edit: 2012-03-25 20:23:45
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.