Giải bài trực tuyến

Vào năm 2026, do sự phát triển mạnh của nhiều ngành công nghệ, nhân loại đã phát minh ra một loại cây nhân tạo có thể giúp con người leo lên được tới cung trăng để du lịch (hay tìm Hằng Nga chẳng hạn). Chi phí để mua cây này khá là đắt đỏ (du lịch cung trăng thì không thể nào rẻ), nên Hạnh quyết định chỉ mua hạt giống của cây rồi đem về trồng, cứ mỗi ngày thì cây lại mọc lên 1 node mới. Lúc Hạnh mới gieo hạt giống xuống đất thì xem như đó là ngày thứ nhất.

Loại cây này có một đặc điểm là:

+ Ở ngày thứ 2, một nhánh mới mọc lên trực tiếp từ hạt giống mới gieo.

+ Ở ngày thứ i (i ≥ 3), nếu node i - 1 và node i - 2 có cùng độ cao thì từ node i - 1 sẽ mọc ra nhánh mới có node i.

+ Ở ngày thứ i (i ≥ 3), nếu node i - 1 và node i - 2 khác nhau về độ cao thì node i - 1 hoặc node i - 2 sẽ mọc ra thêm 1 nhánh mới có node i.

Do khoảng cách từ mặt đất tới cung trăng khá là xa, cả nghìn cây số chẳng hạn,  Hạnh lo lắng không biết đến khi nào cây mới mọc tới được cung trăng. Do đó Hạnh quyết định tìm cao nhân giúp Hạnh tính độ cao cây trung bình từ tất cả các trạng thái có thể xảy ra sau n ngày.

Độ cao cây được tính là số cạnh nhiều nhất trên đường đi từ gốc đến một đỉnh nào đó.

Input

Dòng đầu là số nguyên dương T (T ≤ 10⁶), số test case.

T dòng sau, mỗi dòng là một số nguyên N (N ≤ 10⁶).

Output

Với mỗi dòng trong T dòng, in ra kết quả tương ứng của bài toán. Lưu ý: Lấy phần nguyên của kết quả.

Example

Input:
5
1
2
3
4
5

Output:
0
1
1
2
3
 
Giải thích:
Ở test case 1: Ngày đầu tiên chỉ mới gieo hạt nên cây chưa có độ cao.
Ở test case 2: Ngày thứ hai cây cũng chỉ mới mọc ra một nhánh lên độ cao trung bình là 1.
Ở test case 3: Độ cao trung bình là (2 + 1) / 2 = 1.5.
https://drive.google.com/open?id=0B_Imy46KMUtndnBOWjRSaDZ6aUE
Ở test case 4: Độ cao trung bình là (3 + 2 + 2) / 3 = 2.333.
https://drive.google.com/open?id=0B_Imy46KMUtneHljUG96R3J1ZXc
Ở test case 5: Độ cao trung bình là (3 + 3 + 4 + 2 + 3) / 5 = 3