时间限制：C/C++/Rust/Pascal 6秒，其他语言12秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
题目描述
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 , divisors of
naturally form a partially ordered set under divisibility. We denote the Hasse diagram formed with divisors of
by
. For any two divisors
,
of
, an arc
belongs to
if and only if there exists a prime number
such that
.
has been shown below.
Formally, let be the number of edges that belong to
. If the number in the input is
, then your program should output
.
输入描述:
The first line contains a single integer(
)--- the number of test cases. The next
The only line of each test case contains one integer
(
).
输出描述:
For each test case, output the answer modulo
.