You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Background

最近cjx玩愚者进行愚弄仪式，耀阳、盈月、天穹、梦境甚至是神灵都被他愚弄了，然鹅他的主板寄掉了，他不能进行愚者仪式了。这时候愚者对他说如果他和愚者进行一场游戏，如果他赢了就给他愚弄主板，让主板再也不会坏。你可以帮助cjx继续玩愚者吗？ 游戏规则如下：

Description

1、有一个灵魂方舟用来存储灵魂能量，最初灵魂方舟中灵魂能量为0，存储上线是n(2<=n<=1e9)。

2、cjx和愚者轮流向灵魂方舟中投入灵魂能量，每次投入的灵魂能量必须是正整数，并且不能超过m(1<=m<n)。

3、最终使得灵魂方舟中的灵魂能量达到上限即n的一方获胜。

4、cjx先手并且可以选择m的大小。

Format

Input

输入数据首先包含一个正整数t(t<=1e3)，表示包含t组测试用例，然后是t行数据，每行包含一个正整数n，n的含义参见上面提到的规则。

Output

对于每组数据，如果存在一个数m使得cjx胜利，输出最大的m；如果不存在则输出0.

Samples

2
3
4

1
2

Limitation

1s, 1024KiB for each test case.