Cho số nguyên dương \(n\) và dãy số nguyên dương \(a_{1},a_{2},\ldots,a_{n}\).

Yêu cầu: Hãy cho biết với mỗi số \(a_{i}\ (1 \leq i \leq 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ố?

Dữ liệu vào:

+ Dòng đầu ghi số nguyên dương \(n\ \left( n \leq 10^{3} \right)\);

+ Dòng thứ 2 ghi lần lượt các số \(a_{1},a_{2},\ldots,a_{n}\ ({1 \leq a}_{i} \leq 10^{6})\).

Dữ liệu ra: Ghi \(n\) dòng, dòng thứ \(i\) cho biết số lượng bộ 3 số \(\left( p_{1},p_{2},p_{3} \right)\) sao cho \(p_{1} + p_{2}^{2} + p_{3}^{3} = a_{i}\).

Ví dụ:

Giải thích ví dụ:

+ Số 18 không có bộ 3 số nào thỏa mãn yêu cầu;

+ Số 81 có 2 bộ 3 số là \((29,5,3)\) và \((5,\ 7,\ 3)\).

Ràng buộc:

+ Có 30% số test tương ứng với 30% số điểm có \(n \leq 10\); \({1 \leq a}_{i} \leq 100\);

+ Có 40% số test khác tương ứng với 40% số điểm có \(n \leq 100;1 \leq a_{i} \leq 10^{5};\)

+ Có 30% số test còn lại tương ứng với 30% số điểm không có ràng buộc gì thêm.