Mô tả

Hôm nay tiết học của thầy Male dạy về toán số. Cuối tiết, thầy đề cập đến số Fibonacci và giao bài tập về nhà với dãy này. Số Fibonacci là các số 1, 1, 2, 3, 5, 8, 13, 21, ... được biểu diễn tổng quát như sau:

F[1] = F[2] = 1.
F[n] = F[n-1] + F[n-2] (n > 2).

Yêu cầu: Hãy đếm xem trong n số Fibonacci đầu tiên có bao nhiêu số chia hết cho 3.

Input

- Dòng đầu tiên gồm một số nguyên dương q — số bài tập thầy Male giao (q ≤ 10^6).
- q dòng tiếp theo, mỗi dòng chứa một số nguyên dương n (n ≤ 10^9).

Output

- In ra q dòng, mỗi dòng là kết quả của bài toán.

Scoring

- Subtask 1 (20 điểm): q ≤ 10^3, n ≤ 50.
- Subtask 2 (20 điểm): q ≤ 10^6, n ≤ 50.
- Subtask 3 (20 điểm): q ≤ 10^3, n ≤ 10^3.
- Subtask 4 (20 điểm): q ≤ 10^6, n ≤ 10^6.
- Subtask 5 (20 điểm): q ≤ 10^6, n ≤ 10^9.

Ví dụ

input
2
3
10

output
0
2

Ghi chú

Trong 10 số Fibonacci đầu tiên là 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 có 2 số chia hết cho 3 là 3 và 21.