买瓜

题目背景

小路去买瓜, 挑选完准备称量的时候, 他发现摊主为了展现自己的诚信, 拿出了一个大天平(没有游码)和一排砝码, 经过一番调平, 摊主开始称重, 小路却发现摊主好像并不按照天平的标准操作左物右码, 而是在两边都放一些砝码, 最后再通过计算得出西瓜重量.

几分钟后, 摊主称量出了西瓜的重量, 但是为了考验小路的智商, 摊主决定考小路一题, 否则就卖给小路生瓜蛋子.

小路觉得很为难, 于是他找到了聪明的你, 请你帮他解决这个问题.

题目描述

构造一个包含 $n \enspace (n\leq 10^{18})$ 个整数的序列

使得 $1\sim k$ 中所有整数都可被序列中任意个元素相加减得到

求最大的 $k$ $\left(\rm{mod} \enspace 2^{32}\right)$

输入格式

第一行是一个正整数 $T \leq 500$, 表示数据的组数

接下来 $T$ 行, 每行一个正整数 $n\leq 10^{18}$, 表示需要构造的序列长度

保证 $\sum{n} \leq 10^{18}$

输出格式

共 $T$ 行, 每行一个整数 $k$, 表示相应的答案

输入输出样例

样例输入

2
2
3

样例输出

4
13

样例解释

第一组数据, 序列为 $[1, 3]$，$1=1$，$2=3-1$，$3=3$，$4=3+1$, 答案为 $4$