Yêu cầu: Cho $Q$ câu hỏi, mỗi câu hỏi dạng sau: Hãy đếm các số là bội của 3 hoặc 7 trong phạm vi không vượt quá $N$ ($N$ là số nguyên dương).

Input

Dòng đầu là số tự nhiên $Q$ là số câu hỏi ($1\hspace{0.17em}\le \hspace{0.17em}Q\hspace{0.17em}\le \hspace{0.17em}100$).

$Q$ dòng sau, mỗi dòng ghi một số nguyên dương $N$ ($3\hspace{0.17em}\le \hspace{0.17em}N\hspace{0.17em}\le \hspace{0.17em}{10}^{12}$).

Output In ra số các bội của 3 hoặc 7 tương ứng với từng câu hỏi, được ghi trên từng dòng.

Scoring

• Có 50% số điểm ứng với các test có $Q\hspace{0.17em}\le \hspace{0.17em}100$, $3\hspace{0.17em}\le \hspace{0.17em}N\hspace{0.17em}\le \hspace{0.17em}{10}^6$.

• Có 50% số điểm ứng với các test có $Q\hspace{0.17em}\le \hspace{0.17em}100$, ${10}^7\hspace{0.17em}<\hspace{0.17em}N\hspace{0.17em}\le \hspace{0.17em}{10}^{12}$.

Example

Input

2
6
14

Output

2
6

Note

• Trong phạm vi [$1,\hspace{0.17em}6$] có 2 số là bội của 3 hoặc 7, là 3 và 6.

• Trong phạm vi [$1,\hspace{0.17em}14$] có 6 số là bội của 3 hoặc 7, là 3, 6, 7, 9, 12, 14.