胡安和他的朋友们将把自己分成 $$$n$$$ 队并参加修改后的双败淘汰赛足球锦标赛,其中包括 获奖者' 组和 失败者' 组。最初,所有球队都属于胜者组。
在比赛的每一轮中,只要其中一组完成以下操作,就会发生以下情况: 至少两个 团队:
- 胜者组的所有队伍配对。
- 如果获胜者组中的球队数量为奇数,则会有一支球队没有配对(并且不会参加比赛)。该队留在胜者组。
- 对于配对的胜者组,每组进行一场足球比赛,其中有 没有关系.
- 如果一支球队获胜,则将留在胜者组中。
- 如果一支球队输了,则该球队将跌入败者组 下一轮.
- 败者组的所有队伍配对。
- 如果败者组中有奇数支球队,则将有一支球队没有配对(并且不会参加比赛)。该队留在败者组。
- 对于配对的失败者组中的球队,每组进行一场足球比赛,其中有 没有关系.
- 如果一支球队获胜,则留在败者组。
- 如果一支球队输了,它将被淘汰出锦标赛。
注意,在上述过程中,当胜者组中的球队输掉一场比赛时,该球队将在下一轮中降入败者组。也就是说,本轮败者组不考虑配对过程。
在上述过程的多次迭代之后,两个小组最终都各有一个团队。当这种情况发生时,两支球队将在一场比赛中对决并产生胜利者。
确定总共进行了多少场比赛。可以证明,无论球队如何配对,无论哪支球队胜负,答案都是一样的。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 100$$$)。测试用例的描述如下。
每个测试用例的唯一行包含一个正整数 $$$n$$$ ($$$2 \le n \le 500$$$) — 团队数量。
输出
对于每个测试用例,打印锦标赛期间进行的比赛总数。
示例
输入复制
223
输出复制
24
注意
在第一个测试用例中,可以证明在宣布胜利者之前恰好进行了 $$$2$$$ 场比赛。
在第二个测试用例中,下图显示了一个可能的锦标赛。请注意,总共进行了 $$$4$$$ 场比赛。