5408: Hasse Diagram

Yukikaze is learning discrete mathematics and number theory. A Hasse diagram is a mathematical diagram in the order theory, which is a simple picture of a finite partially ordered set, forming a drawing of the transitive reduction of the partial order. For an arbitrary positive integer n, divisors of n naturally form a partially ordered set under divisibility. We denote the Hasse diagram formed with divisors of n by H_n . For any two divisors u,v of n , an arc(u,v) belongs to  Hn if and only if there exists a prime number p such that  u=pv . H₁₂ has been shown below.

Since Yukikaze loves counting, she will give you a number n and ask you to count the number of edges that belong to H₁,H₂,⋯,H_n  then sum them up. Can you solve the problem for her?

Formally, let f(n) be the number of edges that belong to Hn . If the number in the input is n , then your program should output f (i )mod1145140019 .

The first line contains a single integerT (1 ≤T≤5)--- the number of test cases. The next T lines contain the descriptions of all test cases.

The only line of each test case contains one integer n 

For each test case, output the answer modulo 1145140019.

3
1
12
114514

0
27
2493946

0+1+1+2+1+4+1+3+2+4+1+7=270+1+1+2+1+4+1+3+2+4+1+7=27