Description

小猪佩奇和小猪靖崎是一对好朋友，她们无忧无虑的生活在糖果屋里，因此她们都很胖。

现在给她们两只猪猪一共N个糖果，每个糖果下标依次从1~N。她们要一起吃掉这些糖果。

但是小猪靖崎不允许自己再这么胖下去，（再这么胖下去可是要被拿去卖钱的呀QAQ毕竟猪肉这么贵）。所以她只吃想吃一个糖果，剩下的全给小猪佩奇。所以让小猪佩奇一开始挑一个糖果给她。

小猪靖崎喜欢偶数而且喜欢last这个英语单词，所以她说，佩奇你每次都吃奇数位置的糖果，剩下的糖果重新按照从1开始对齐。重复多次，然后把最后一个剩下的糖果给我就行啦~。

佩奇听了脑袋都大了，她的脑袋里就只有吃。请你帮帮佩奇完成靖崎的难题，请输出给小猪靖崎的糖果最初始的位置是多少？

小猪靖崎会询问q次，每次的N都不一样。

Input Format

第一行q次询问

接下q行是每次询问的N，有N个糖果。

（1<=N<=1e9，1<=q<=1e6）

Output Format

输出一个数，这个数是小猪佩奇应该一开始把下标为多少的糖果给小猪靖崎。

2
1
2

1
2