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 ≤ Q ≤ 100~).

Q dòng sau, mỗi dòng ghi một số nguyên dương ~N~ (~3 ≤ N ≤ 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 ≤ 100, 3 ≤ N ≤ 10^6~.

Có 50% số điểm ứng với các test có ~Q ≤ 100, 10^7 < N ≤ 10^{12}~.

Example

Input

2
6
14

Output

2
6

Note

Trong phạm vi ~[1, 6]~ có 2 số là bội của 3 hoặc 7, là 3 và 6.

Trong phạm vi ~[1, 14]~ có 6 số là bội của 3 hoặc 7, là 3, 6, 7, 9, 12, 14.