kotori和一些偶像们围成一圈，一共有n个偶像（包括kotori自己），她们的序号顺时针从1到n。现在她们从1号开始进行顺时针报数：1,2,1,2,1……
每个报到2的人出列。直到剩下最后一个人为止。那么这个剩下的人就能被选中发专辑出道啦！
kotori可以暗箱操作决定自己的序号。她很想发专辑，于是向聪明的你求助，初始序号设定为多少才可以呢？
第一行输入一个正整数t，代表共有t组样例。
第2行到第t+1行，每行一个正整数n，代表一次询问。
(1≤t≤10000，1≤n≤10^18)
一共t行，每行一个正整数，代表kotori的初始序号。