Cho số tự nhiên \(N\).

Nhiệm vụ của bạn là đếm tất cả các số có đúng ba ước số.

Ví dụ \(n=100\), ta có các số \(4\).

Input

• Dòng đầu tiên đưa vào số lượng test \(T\ (1 \le T \le 100)\).
• Những dòng kế tiếp đưa vào các bộ test. Mỗi bộ test là một số \(N\ (1 \le N \le 10^{12})\).

Output

• Đưa ra kết quả mỗi test theo từng dòng.

Example

2
50
200

4
6