Cho số nguyên dương N (1<= N <=10^9) nhiệm vụ của bạn là đếm xem có bao nhiêu số nguyên dương không vượt quá N mà chia hết cho 5 hoặc chia hết cho 3

Input

Dòng đầu là số trường hợp kiểm thử ~t (1 \le t \le 100)~

Tiếp theo gồm ~t~ dòng mỗi dòng chứa số nguyên dương N (1<= N <=10^9)

Output

Gồm ~t~ dòng mỗi dòng là một số nguyên là kết quả của bài toán

Ví dụ

Input

3
12
20
31

Output

6
9
14

Giải thích

Ở test 1 gồm các số : ~3,5,6,9,10,12~

Ở test 2 gồm các số : ~3,5,6,9,10,12,15,18,20~

Ở test 3 gồm các số : ~3,5,6,9,10,12,15,18,20,21,24,25,27,30~