SPOJ.com - Problem NUMTRY

NUMTRY - Number Theory

#fast-prime-factorization

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

f(n) = ∏( p_i^2e_i+1+1 ), where p_i is prime factor of n and e_i is highest power of p_i 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 ).

Submit solution!

hide comments

< Previous 1 2 Next >

	Yashpal: 2014-12-31 19:55:28 Awesome Problem !! Reduced in Simple formula ! :) Last edit: 2014-12-31 20:16:47
	Viplov Jain: 2014-06-22 15:29:09 @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
	[Lakshman]: 2014-06-07 13:47:00 Finally accepted took three moths to solve this problem. (Re:xeronix) : Great :) Last edit: 2014-06-07 13:44:40
	[Lakshman]: 2014-06-07 13:47:00 @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
	[Lakshman]: 2014-06-07 13:47:00 @XeRo!NiX can you please suggest me some optimistion Last edit: 2014-02-25 08:36:21
	apia: 2014-06-07 13:47:00 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
	teoy: 2014-06-07 13:47:00 the time limit is for one case or all cases ?
	Damian Straszak: 2014-06-07 13:47:00 the tutorial version is very helpful, thank you
	Damian Straszak: 2014-06-07 13:47:00 Ok, so this is tough. I Have no idea how to speed up my code. Any hints :)?
	Damian Straszak: 2014-06-07 13:47:00 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

Submit solution!

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