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ụ: