Số \(X\) được gọi là số đẹp nếu \(X\) là số nguyên dương lớn hơn 1 và có đúng 3 ước số .

Ví dụ: số 4 có đúng 3 ước là: \(\{ 1,\ 2,\ 4\}\) nên 4 là số đẹp; số 6 có 4 ước số là: \(\{ 1,\ 2,\ 3,\ 6\}\) nên 6 không phải là số đẹp.

Yêu cầu: Cho \(T\ \)truy vấn, với truy vấn thứ \(i\ (1 \leq i \leq T)\): cho một số nguyên dương \(a_{i}\), hãy xác định số lượng số đẹp có trong phạm vi từ \(1\) đến \(a_{i}\).

Dữ liệu vào:

+ Dòng thứ nhất chứa duy nhất số nguyên dương \(T\ (1 \leq T \leq 10^{6}\)) ;

+ Dòng thứ \(i\) trong \(T\) dòng tiếp theo chứa một số nguyên dương \(a_{i}\ (1 \leq a_{i} \leq 10^{6})\).

Dữ liệu ra:

+ ghi \(T\) dòng, dòng thứ \(i\) trong \(T\) dòng ghi một số nguyên dương duy nhất là kết quả của truy vấn thứ \(i.\)

Ví dụ: