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

1
1

0

2
10 25

4
16

10
123456789 234567890 345678901 456789012 567890123 678901234 789012345 890123456 901234567 12345678

645956573
1273061974
1916838059
2571642223
3234719854
3903895878
4573092218
5191744600
5259963415
55955605