All Tracks Math Number Theory Problem

GCD problem
/

Greatest common divisor, Mathematics, Medium-Hard, Mobius Inversion, Number Theory

Problem
Editorial
Analytics

For each set of four integers given \((i,j ,k,l)\) where \(1\leq i < j <k <l \leq N\). You are required to compute the following:

\(\displaystyle\sum_{i=1}^{N} \displaystyle\sum_{j=i+1}^{N}\displaystyle\sum_{k=j+1}^{N} \displaystyle\sum_{l=k+1}^{N} gcd(i,j,k,l) ^{4}\)

Input format

  • First line: \(T\) that denotes the number of test cases
  • Next \(T\) lines: A integer \(N\)

Output format

Print the answer for each test case \(Mod \,\,\,10^9+7\) in a new line.

Constraints
\(1 \leq T \leq 10 \\ 1 \leq N \leq 10^5\)

SAMPLE INPUT
2
4
5
SAMPLE OUTPUT
1
5
Explanation

For First Test case N=4 :
(1,2,3,4) :   gcd(1,2,3,4)4 = 1
Total sum = 1

For Second Test Case N=5 :
(1,2,3,4) :   gcd(1,2,3,4)4 = 1
(1,2,3,5) :   gcd(1,2,3,5)4 = 1
(1,2,4,5) :   gcd(1,2,4,5)4 = 1
(1,3,4,5) :   gcd(1,3,4,5)4 = 1
(2,3,4,5) :   gcd(2,3,4,5)4 = 1
Total sum = 1+1+1+1+1 = 5

Time Limit: 5.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB

Best Submission

Similar Problems

Contributors

This Problem was Asked in

Initializing Code Editor...
Notifications
View All Notifications

?