Cho ~T~ truy vấn. Mỗi truy vấn cho một số nguyên dương ~N~.

Yêu cầu

Đếm số lượng số nguyên dương không vượt quá ~N~ chia hết cho ~3~ hoặc ~5~.

Input

Dòng đầu chứa số nguyên ~T~ ~(1 \le T \le 10^5)~.

~T~ dòng tiếp theo, mỗi dòng chứa một số nguyên ~N~ ~(1 \le N \le 10^{12})~.

Output

In ra ~T~ dòng, mỗi dòng là đáp án của một truy vấn.

Subtask

• 80% số điểm: ~1 \le T \le 10^4~, ~1 \le N \le 10^2~.
• 20% số điểm: ~10^4 < T \le 10^5~, ~10^2 < N \le 10^{12}~.

Ví dụ

3
3
5
20

1
2
9