Đây là đề Training Python 3

Tuần làm việc của bạn gồm ~n~ ngày được đánh số từ ~1~ tới ~n~, sau ngày thứ ~n~ thì sẽ là ngày thứ ~1~ và tương tự. Và ~3~ ngày trong tuần sẽ là ngày nghỉ (zè ze :D). Một ngày nghỉ là ngày thứ ~n~, ngày cuối cùng trong tuần. Nhiệm vụ của bạn là chọn ~2~ ngày nghỉ còn lại, sao cho:

• Không có ~2~ ngày nghỉ nào kề nhau. Có nghĩa là bạn không thể chọn ngày ~1~ là ngày nghỉ vì ngày ~1~ là ngày tiếp theo của ngày ~n~.

• Bạn cần chia các ngày nghỉ sao cho tối ưu nhất có thể, có nghĩa là, nếu chia ngày nghỉ ra làm ~3~ đoạn có độ dài ~a1~, ~a2~, ~a3~, thì ta cần tối ưu sao cho ~min(|a1 - a2|, |a2 - a3|, |a3 - a1|)~ là lớn nhất

Input

Dòng đầu tiên chứa ~1~ số t duy nhất ~(1 \le t \le 1000)~ - số lượng test cases.

~t~ dòng tiếp theo mỗi dòng chứa ~1~ số nguyên n duy nhất ~n~ ~(6 \le n \le 10^9)~

Output

Đối với mỗi test case, output là ~1~ số nguyên - giá trị ~min(|a1 - a2|, |a2 - l3|, |a3 - a1|)~ là lớn nhất

Examples

Input

3
6
10
1033

Output

0
1
342

Note

Hình dưới đây mô tả ~2~ test case. Ngày nghỉ được đánh dấu màu tím, ngày nghỉ mặc định được đánh dấu màu đỏ, khoảng thời gian làm việc được gạch chân màu xanh lá cây.

• Trong testcase ~1~, có duy nhất một cách chọn ngày nghỉ đó là chọn ngày ~2~, ~3~ và ~4~( vì ngày ~1~ và ngày ~5~ là những ngày nằm bên cạnh ngày ~n~). Vì vậy chỉ có duy nhất ~1~ cách chọn những ngày nghỉ mà không bị liền kề nhau, đó là chọn ngày ~2~ và ngày 4. ~a1~ = ~a2~ = ~a3~ = 1, đáp án ~min(|a1 − a2|,|a2 - l3|, |a3 - a1|)~=0.

• Trong test case ~2~, một trong những cách chọn được trình bày dưới đây, ta có thể chọn ngày ~3~ và ngày ~5~ là ngày nghỉ.

Vậy đáp án tối ưu theo yêu cầu của đề bài sẽ là ~1~ = ~min (1,3,2)~ = ~min (| 2 − 1 |, | 1 − 4 |, | 4 − 2 |)~. Có thể chỉ ra được rằng không thể có cách chọn ngày nghỉ nào có thể cho ra đáp án lớn hơn.