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