题目描述

一天晚上，Rainbow Dash 和 Fluttershy 想出了一个游戏。由于小马们是朋友，她们决定在游戏中不进行竞争，而是追求共同的目标。

游戏开始于一个正方形的平面网格，初始时网格的轮廓边界已经搭建好。Rainbow Dash 拥有无限数量的浅蓝色 $1\times1$ 方块，Fluttershy 拥有无限数量的黄色 $1\times1$ 方块。

方块的放置规则如下：每次新放置的方块，必须通过一条边与之前回合中已搭建的结构相邻（注意，网格的轮廓边界初始时已搭建好）。每一回合，一只小马可以根据游戏规则放置任意数量属于她颜色的方块。

Rainbow Dash 和 Fluttershy 发现，她们可以通过这种方式在网格上构建各种图案。她们决定从简单的开始，于是决定将方块按棋盘格的方式铺满整个网格。Rainbow Dash 以速度著称，因此她关心她和 Fluttershy 至少需要多少回合，才能用方块铺满整个网格并形成棋盘格图案。请你帮她计算这个最小回合数！

由于小马们可能会在不同大小的棋盘上多次进行游戏，Rainbow Dash 请你计算多个不同大小网格的最小回合数。

两种颜色的棋盘格图案指的是：每个方格仅与颜色不同的方格通过边相邻。

输入格式

第一行包含一个整数 $T$（$1 \le T \le 100$），表示游戏网格的数量。

接下来的 $T$ 行，每行包含一个整数 $n$（$1 \le n \le 10^9$），表示游戏网格的边长。

输出格式

对于每个游戏网格，输出用方块铺满形成棋盘格图案所需的最小回合数。

说明/提示

对于 $3\times3$ 的网格，小马们可以用两步完成棋盘格铺设：

由 ChatGPT 4.1 翻译

样例

2
3
4

2
3