Bờm là một người yêu thích Toán học và rất thích các số nguyên tố. Chính vì thế nên cậu ta đã tự định nghĩa số tự nhiên nào là đẹp, là không đẹp. Một số tự nhiên X là số đẹp nếu như nó có thể biểu diễn dưới dạng p*q²*r³ trong đó p, q, r là các số nguyên tố khác nhau. Tất nhiên nếu cho 1 số tự nhiên rồi kiểm tra xem nó có phải là một số đẹp hay không cũng không hề đơn giản. Tuy nhiên bài toán này sẽ càng trở nên thú vị hơn nếu như bạn có thể đếm được  số lượng số đẹp trong đoạn [1, N] với N là một số tự nhiên cho trước.

Dữ liệu: Vào từ file PRIME.INP gồm:

• Dòng đầu tiên chứa số nguyên T là số lượng test (T <= 4)
• T dòng tiếp theo mỗi dòng chứa một số tự nhiên N (1 <= N <= 10⁹)

Kết quả: Ghi ra file PRIME.OUT là T dòng tương ứng là kết quả của T test.

Ví dụ: