Số tự nhiên $N$ được gọi là số Sphenic nếu $N$ là tích của chính xác ba số nguyên tố khác nhau. Một vài số Sphenic đầu tiên là: 30, 42, 66, 70, 78, 102, 105, 110, 114,...

Cho một số $N$, nhiệm vụ của bạn là kiểm tra xem đó có phải là số Sphenic hay không.

Ví dụ: $N$ = 30 = 2 x 3 x 5 là số Sphenic, còn $60 = 2^2$ x 3 x 5 thì không phải vì thừa số 2 có số mũ lớn hơn 1.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên $T$ là số bộ dữ liệu vào kiểm tra, mỗi bộ dữ liệu vào gồm một dòng chứa một số nguyên dương $N$.

Ràng buộc:

• $0 < T \leq 100; 0 < n \leq 10^6.$

Kết quả

• in ra $T$ dòng, nếu số nguyên $N$ từ đầu vào là số Sphenic thì in ra số số 1, ngược lại in ra 0.

Ví dụ: