Cho số nguyên \(n (1\le n\le 10^{14}\)). Hãy đếm số cặp \((a,b)\) thỏa mãn:

• \(1\le a < b\le n\);
• \(a\) x \(b\) là một số chính phương.

Bài toán đặt ra cho \(q\) truy vấn, hãy tìm câu trả lời cho mỗi truy vấn. Vì kết quả có thể lớn, hãy xuất nó theo modulo \(977555333311111.\)

Input

• Dòng đầu tiên chứa số nguyên dương \(q\);
• Dòng thứ hai chứa \(q\) truy vấn số nguyên dương \(n_1, n_2, ..., n_q\).

Output

• Gồm q dòng mỗi dòng là một số duy nhất là câu trả lời cho truy vấn \(n_q\) theo modulo \(977555333311111.\)

Ví dụ 1

Input

1
1

Output

0

Giải thích: Không có cặp số nguyên \((a,b)\) nào thỏa mãn với \((1\le a < b \le 1\)).

Ví dụ 2

Input

2
10 25

Output

4 
16

Giải thích

• Trong truy vấn đầu tiên, có \(4\) cặp thỏa mãn: \((1,4), (1,9), (2,8), (4,9).\)
• Trong truy vấn thứ hai, có \(16\) cặp thỏa mãn: \((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).\)

Ràng buộc

• Subtask 1: \(16.67\)% tests for \(q = 1\) và \(1 \leq n \leq 10^6\);

• Subtask 2: \(16.67\)% tests for \(q = 1\) và \(1 \leq n \leq 10^{14}\);

• Subtask 3: \(16.67\)% tests for \(1 \leq q \leq 10\) và \(1 \leq n \leq 10^{12}\);

• Subtask 4: \(16.67\)% tests for \(1 \leq q \leq 100\) và \(1 \leq n \leq 10^{10}\);

• Subtask 5: \(16.67\)% tests for \(1 \leq q \leq 1000\) và \(1 \leq n \leq 10^8\);

• Subtask 6: \(16.67\)% tests for \(1 \leq q \leq 10.000\) và \(1 \leq n \leq 10^6\).