Processing math: 100%

重建炮台

时间限制: 1000 ms 内存限制: 131072 kb
总通过人数: 0 总提交人数: 0

题目描述

X 国的国土可以近似认为是一个正 2n1 边形。为了防备其他国家的入侵,许多年前 X 国在其边境线的每个拐点处(即正 2n1 边形的顶点)都设置了一座防御塔。

然而由于已经过了太多年,过去修建的防御塔已经变得落后于现在的科技水平太多。为此,需要重建一些防御塔。显然,如果只沿着边境线走,从一座防御塔走到另一座不同的防御塔有两条路径(分别沿着边境线顺时针走和逆时针走)。经过专家研究,如果两座重建的防御塔之间的两条上述路径中,存在至少一条路径,满足这条路径上经过的防御塔数(不含起点和终点的防御塔)恰有 n 座,则称对于这两座防御塔,资源得到了充分利用

重建防御塔需要花费大量的资金,为了使缴纳税金的公民们相信资金得到了有效的使用,重建的防御塔中必须存在至少一对不同的防御塔,满足对于这两座防御塔,资源得到了充分利用。日理万机的 X 国总统无暇认真考虑重建方案,只给了菜菜的下级quintessence一个重建防御塔的数目 K 作为指示。quintessence接到重建 K 座防御塔的指令后,只会不加任何思考地随机从所有防御塔中选择 K 座进行重建。然而机智的总统早就预料到了一切,他给出的数值 K 满足:不论怎么选择某 K 座防御塔进行重建,都会存在至少一对重建防御塔的资源得到了充分利用,而且他给出的数值恰好是满足条件的最小值

那么问题来了,总统给出的 K 是多少呢?

输入

第一行包含一个数 T,表示数据组数。

接下来 T 行,每行包含一个整数 n

保证 1T10000, 3n10000

输出

对于每组数据,输出一行,包含一个整数,表示 K 的值。

输入样例

1
3

输出样例

3

相关推荐