Cho số nguyên dương \(n\) và dãy số nguyên dương \(a_1, a_2...a_n\)

Yêu cầu: Hãy cho biết với mỗi số \(a_i (1 \le i \le n)\) có bao nhiêu bộ \(3\) số \((p_1, p_2, p_3)\) sao cho \(p_1 + {p_2}^2 + {p_3}^3 = a_i\), trong đó \(p_1, p_2, p_3\) là các số nguyên tố?

Input

• Dòng đầu ghi số nguyên \(n (n \le 10^3)\)
• Dòng thứ 2 ghi lần lượt các số \(a_1, a_2, ... a_n (1 \le a_i \le 10^6)\)

Output

• Ghi \(n\) dòng, dòng thứ \(i\) cho biết số lượng bộ \(3\) số \((p_1, p_2, p_3)\) sao cho \(p_1 + {p_2}^2 + {p_3}^3 = a_i\)

Ràng buộc

• 30% số test có \(n \le 10\) và \(1 \le a_i \le 100\)
• 40% số test có \(n \le 100\) và \(1 \le a_i \le 10^5\)
• 30% số test còn lại không ràng buộc gì thêm

Sample Input 1

2
18 81

Sample Output 1

0
2

Giải thích

Số 18 không có bộ 3 thỏa mãn
Số 81 có 2 bộ 3 là (29,5,3) và (5,7,3)