“桃之夭夭，灼灼其华。”

园艺师 awdec 和魔法师 Fantasy_Blue 共同承包了一片狭长的花园。花园里有一排连续的 个空花坑。此时，运货商送来了 棵桃树幼苗，它们的高度两两不同，我们可以将其高度分别记为 。
awdec 喜欢阶梯般的层次感，而 Fantasy_Blue 则偏爱参差不齐的错落感。两人决定通过一场博弈游戏来完成这排桃树的栽种。
初始时，花园里有一个长度为 的序列 ，所有位置均为空（代表空花坑），同时有 棵高度为 的桃树尚未被栽种。
awdec 和 Fantasy_Blue 轮流进行操作，由 awdec 先手。在每次操作中，当前玩家需要执行以下动作：
从尚未栽种的桃树中选择一棵（即选择一个尚未使用的数值 ）。
在花园中选择一个尚未栽种桃树的空花坑（即选择序列 中一个尚为空的位置 ）。
将这棵树种进去（即令 ）。
当 轮操作结束后，所有的花坑都会被填满，此时会形成一个完整的排列 。
awdec 希望最终排列 的最长上升子序列长度尽可能大，而 Fantasy_Blue 希望这个长度尽可能小。
假设两人足够聪明，均采取最优策略，请你求出最终排列 的最长上升子序列长度。

【名词解释】
长度为 的排列：由 这 个整数、按任意顺序组成的数组（每个整数均恰好出现一次）。例如， 是一个长度为 的排列，而 和 都不是排列，因为前者存在重复元素，后者包含了超出范围的数。
上升子序列：对于数组的某个非空子序列 （），若满足 ，则称这个子序列是一个上升子序列。
子序列：从原字符串中删除任意个（可以为零、可以为全部）字符得到的新字符串。

每个测试文件均包含多组测试数据。第一行输入一个整数  代表数据组数，每组测试数据描述如下：

第一行输入一个正整数 ，表示序列的长度（即桃树和花坑的数量）。

对于每一组测试数据，在一行上输出一个整数，代表在双方均采取最优策略的情况下，最终排列  的最长上升子序列长度。

2
1
2

1
2

对于  的情况，唯一的桃树（高度为 ）只能种在唯一的位置，最终序列为 ，最长上升子序列长度为 。
对于  的情况：
 先手 awdec 为了最大化上升子序列，会选择将高度为  的树种在第  个位置，此时序列为 。
 后手 Fantasy_Blue 只能将剩下高度为  的树种在第  个位置，最终序列为 。
 此时最终序列的最长上升子序列为 ，长度为 。
 （如果先手 awdec 将高度为  的树种在第  个位置，后手会将高度为  的树种在第  个位置，序列变为 ，长度变为 。但先手十分聪明，会采取对自己最优的策略，因此结果为 。）