Dota 2 是一款由 Valve 开发并发布的多人在线战术竞技游戏（MOBA）。Dota 2 的比赛在两支五人队伍之间进行，每支队伍在地图上占据并防守各自的基地。十名玩家中的每一位都独立控制一个强大的角色，称为“英雄”，他们拥有独特的技能和不同的游戏风格。在比赛中，玩家通过收集经验值和物品来帮助他们的英雄击败对方队伍的英雄。率先摧毁对方基地内的大型建筑“遗迹”（Ancient）的队伍获胜。

国际邀请赛（The International）是 Dota 2 的年度电子竞技世界锦标赛，由游戏开发商 Valve 主办和制作。锦标赛由 18 支队伍组成；12 支队伍根据 Dota 职业巡回赛（Dota Pro Circuit）的最终结果确定，另外 6 支队伍通过北美、南美、东南亚、中国、东欧和西欧地区的区域预选赛胜出。

在 3021 年，国际邀请赛在中国桂林举行。和 1000 年前一样，中国的 LGD 战队将再次对阵俄罗斯的 Spirit 战队。随着锦标赛的发展，规则是采用 $n$ 局 $n$ 胜制（$n$ 为奇数），因此一支队伍至少需要赢得 $\frac{n+1}{2}$ 局比赛才能获得冠军。（在 2021 年，$n$ 仅为 5，Spirit 战队以 3:2 获胜）。

在比赛开始前，队伍可以选择禁用（ban）特定英雄，使其不能被对手使用。在这 1000 年间，大家都知道 Spirit 战队非常擅长使用一个叫 Magnus 的英雄，这曾帮助他们在 2021 年击败了 LGD 战队。

尽管大家都认为 LGD 战队从一开始就会选择禁用 Magnus，但 LGD 战队的想法却不同。他们认为自己足够强大，可以击败对手的 Magnus，因此他们只会在第 $x$ 局比赛（如果有的话）开始禁用 Magnus。

为了简化问题，如果 LGD 战队选择禁用 Magnus，他们肯定会赢得该局比赛。否则，他们有 50% 的概率赢得该局比赛。

作为 LGD 战队的粉丝之一，JB 想知道在最坏情况下，LGD 战队能够夺冠所需的最小 $n$ 是多少。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 10^5$)，表示测试用例的数量。

接下来的 $T$ 行中，每行包含一个整数 $x$ ($1 \le x \le 2 \times 10^9$)，表示 LGD 战队将从第 $x$ 局比赛开始禁用 Magnus。

输出格式

对于每个测试用例，请在一行中输出一个整数，表示 LGD 战队夺冠所需的最小总局数。

样例

输入格式 1

2
1
3

输出格式 1

1
5

说明

忽略大家最强烈的愿望，测试数据中存在 $x > 1$ 的情况，这意味着 LGD 战队并不总是从一开始就选择禁用 Magnus。