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\)