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≤i≤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≤T≤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≤a_i≤10^6) ~.

Kết quả:

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

Input

2
10
50 

Output

2
4