Số đẹp

Một số nguyên dương \(X\) được gọi là số đẹp nếu:

• \(X > 1\)
• \(X\) có đúng \(3\) ước số nguyên dương.

Ví dụ:

• \(4\) có đúng \(3\) ước số là \(1, 2, 4\) nên \(4\) là số đẹp.
• \(9\) có \(3\) ước là \(1, 3, 9\) nên cũng là số đẹp.
• \(6\) có \(4\) ước là \(1, 2, 3, 6\) nên không phải là số đẹp.

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

Input

Dữ liệu được đọc từ file SODEP.INP:

• Dòng đầu tiên chứa số nguyên \(T\) \((1 \le T \le 10^6)\) --- số truy vấn.
• \(T\) dòng tiếp theo, mỗi dòng chứa một số nguyên \(a_i\) \((1 \le a_i \le 10^6)\) --- giá trị truy vấn thứ \(i\).

Output

Ghi ra file SODEP.OUT \(T\) dòng, mỗi dòng là kết quả của truy vấn tương ứng: số lượng số đẹp từ \(1\) đến \(a_i\).

Example

2
10
50

2
4

Scoring

• \(30\%\) số test ứng với \(T = 1\), \(1 \le a_i \le 10^3\)
• \(40\%\) số test ứng với \(1 \le T \le 10^3\), \(1 \le a_i \le 10^6\)
• \(30\%\) số test ứng với \(1 \le T \le 10^6\), \(1 \le a_i \le 10^12\)