33OJ
登录 注册

#D1039. 公寓入住

公寓入住

题目描述

有一栋 nn 层公寓,楼层编号为 11 到 nn,每层最多住一个人。现在有 nn 个人要依次入住。

  • 第一个人住进第 11 层。
  • 之后每个人在尚未入住的楼层中,选择使“到所有已入住楼层的最小距离”最大的楼层;如果有多个这样的楼层,就选择编号最小的那个。

小 C 想知道:最后一个人会住进第几层?

输入格式

第一行一个整数 TT,表示测试数据组数。

接下来 TT 行,每行一个十进制正整数 nn,以字符串形式给出,没有前导零,表示公寓层数和入住人数。

输出格式

输出 TT 行,每行一个十进制整数,表示对应数据中最后一个人入住的楼层。答案以字符串形式输出,没有前导零。

样例

1
6
5
1
2
2
1
1
1

样例解释

样例 1 中,66 个人依次入住 1,6,3,2,4,51,6,3,2,4,5 层,所以最后一个人住在第 55 层。

样例 2 中,第一个人住 11 层,第二个人住在离 11 层最远的 22 层,所以答案是 22。

样例 3 中只有一层,第一个人就住在第 11 层,所以答案是 11。

数据范围与约定

子任务 分值 限制
11 3030 1≤n≤10181 \le n \le 10^{18}
22 7070 nn 的十进制位数不超过 10510^5(可能超过任何内置整数类型)

对于 100%100\% 的数据,保证 1≤T≤101 \le T \le 10,nn 是正整数且没有前导零。