[Variants] An interesting counting problem related to square product task A

Tác giả:

SPyofgame

Dạng bài

Điểm: 500 (p) Thời gian: 1.0s Bộ nhớ: 1G Input: bàn phím Output: màn hình

Given \(q\) queries, you must find answer for each query.

For each query, you are given an positive integer \(n\ (1 \leq n \leq 10^{14})\).

Count the number of pairs \((a, b)\) that satisfies:

\(1 \leq a < b \leq n\)
\(a \times b\) is a perfect square.

Since the result can be large, output it under modulo \(977555333311111\).

Input

The first line contains a positive integer \(q\).
The second line contains \(q\) queries of positive integer \(n_1, n_2, \dots, n_q\).

Output

In the p-th line, output a single number is the answer for query \(n_p\) under modulo \(977555333311111\).

Scoring

Subtask 1: \(16.67\)% tests for \(q = 1\) and \(1 \leq n \leq 10^6\).
Subtask 2: \(16.67\)% tests for \(q = 1\) and \(1 \leq n \leq 10^{14}\).
Subtask 3: \(16.67\)% tests for \(1 \leq q \leq 10\) and \(1 \leq n \leq 10^{12}\).
Subtask 4: \(16.67\)% tests for \(1 \leq q \leq 100\) and \(1 \leq n \leq 10^{10}\).
Subtask 5: \(16.67\)% tests for \(1 \leq q \leq 1000\) and \(1 \leq n \leq 10^8\).
Subtask 6: \(16.67\)% tests for \(1 \leq q \leq 10.000\) and \(1 \leq n \leq 10^6\).

Example

Test 1

Input

1
1

Output

Note

There are no satisfied integer pair \((a, b)\) that \(1 \leq a < b \leq 1\)

Test 2

Input

2
10 25

Output

4
16

Note

In the first query, there are \(4\) satisfied pairs: {\(1, 4\)}, {\(1, 9\)}, {\(2, 8\)}, {\(4, 9\)}.

In the second query, there are \(16\) satisfied pairs: {\(1, 4\)}, {\(1, 9\)}, {\(1, 16\)}, {\(1, 25\)}, {\(2, 8\)}, {\(2, 18\)}, {\(3, 12\)}, {\(4, 9\)}, {\(4, 16\)}, {\(4, 25\)}, {\(5, 20\)}, {\(6, 24\)}, {\(8, 18\)}, {\(9, 16\)}, {\(9, 25\)}, {\(16, 25\)}.

Test 3

Input

10
123456789 234567890 345678901 456789012 567890123 678901234 789012345 890123456 901234567 12345678

Output

Bình luận

Không có bình luận nào.