Cho số ~N~ nguyên dương ~1\le N \le{10}^{10}~.

Yêu cầu: Đếm số lượng số nguyên dương là bội của ~3~ hoặc ~5~ trong phạm vi từ ~1~ đến ~N~.

INPUT

Đọc từ bàn phím theo cấu trúc sau:

• Dòng thứ nhất chứa số nguyên ~T~ (~1 ≤ T ≤ 100~) cho biết số bộ dữ liệu đầu vào;
• Tiếp theo ~T~ dòng, mỗi dòng chứa một số nguyên dương ~N~.

OUTPUT

• Gồm ~T~ dòng, mỗi dòng tương ứng với mỗi bộ dữ liệu đầu vào, in ra kết quả bài toán.

SAMPLE INPUT 1

3
3
5
10

SAMPLE OUTPUT 1

1
2
5

SUBTASKS

• ~90\%~ số điểm của bài ứng với các bộ dữ liệu vào có giới hạn ~1 ≤ N ≤ 10^6~
• ~10\%~ số điểm của bài ứng với các bộ dữ liệu vào có giới hạn ~10^6 < N \le 10^{10}~.