Cho số nguyên dương ~N~. Hãy đếm các số nguyên dương là bội của 3 hoặc 5 trong phạm vi không quá ~N~.

Input

• Dòng đầu tiên chứa số nguyên ~T~ (~1 \le T \le 10^5~) là số lượng bộ test.
• ~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 chứa kết quả của một bộ test tương ứng.

Sample Input 1

3
3
5
20

Sample Output 1

1
2
9

Giải thích:

• Đoạn ~[1, 3]~ có 1 số chia hết cho 3 hoặc 5 là: 3.
• Đoạn ~[1, 5]~ có 2 số chia hết cho 3 hoặc 5 là: 3, 5.
• Đoạn ~[1, 20]~ có 9 số chia hết cho 3 hoặc 5 là: 3, 5, 6, 9, 10, 12, 15, 18, 20.

Subtasks

• Subtask 1: 80% số test có ~1 \le T \le 10^2; 1 \le N \le 10^4~.
• Subtask 2: 20% số test có ~10^2 < T \le 10^5; 10^4 < N \le 10^{12}~.