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≤i≤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~ ~(n≤10^3)~;
• Dòng thứ 2 ghi lần lượt các số ~a_1,a_2,…,a_n~ ~(1≤a_i≤10^6)~.

Dữ liệu ra: 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:

• Có 30% số test tương ứng với 30% số điểm có ~n≤10~; ~1≤a_i≤100~;
• Có 40% số test khác tương ứng với 40% số điểm có ~n≤100;1≤a_i≤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.

Ví dụ:

Input:

2
18 81 

Output:

0
2 

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ố ~8~1 có 2 bộ 3 số là ~(29,5,3)~ và ~(5,7,3)~.