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.