由于卢宝天天被队友diss，还住进了ICU，对此卢宝一直怀恨在心，因为卢宝知道，自己才是新一届的希望，但自己的两个队友太菜了，卢宝觉得与其带队友躺金不如自己原地芜湖起飞。于是卢宝开始计划一次暗杀行动
在一层宿舍楼内，含有n个宿舍，卢宝的两个队友正在同一间宿舍内休息，但卢宝并不知道他的两个队友住在哪一间宿舍里面，卢宝的队友可能位于n个宿舍内的任意一间，于是卢宝准备了一些的手榴弹准备把所有的宿舍炸掉，但因为手榴弹的动静过于大，卢宝第 i 次丢入房内一个手榴弹，如果当前宿舍内没有队友，那么队友在手榴弹爆炸之后就会从他们当前所停留的宿舍 x 跑到第 x + i 的宿舍去，直到跑到第 n 号房间后没地方了停止逃跑（如果逃跑的房间已经被炸过了，也可以作为躲避的房间，且卢宝也可以再次暗杀之前已经暗杀过的房间，如果逃跑的房间超出n则会停留在n号房间）。那么请问，在其队友随机位于一个房间的情况下，在保证能100%将队友暗杀的情况下，至少需要几个手榴弹？
单组数据输入
第一行一个 t 表示接下来有t行输入（1<=t<=2e7)
每组数据一个数字n，表示含有n个宿舍 （1<=n<=1e15)
请用复杂度低于O(nlogn）的算法
输出一个数，表示在100%保证暗杀成功的条件下卢宝至少需要几个手榴弹
3 1 3 6
1 2 3 样例2： 第1种方案 第一次暗杀第1个房间，如果队友在第1个房间则暗杀成功，如果没有则可能位于2、3房间，此时队友爆炸移动后只可能位于3房间 第二次暗杀第3个房间，此时一定能暗杀成功 此时需要2个手榴弹才能保证将队友暗杀 第2种方案 第一次暗杀第2个房间，如果队友在第2个房间则暗杀成功，如果没有则可能位于1、3房间，此时队友爆炸移动后可能位于2、3房间 第二次暗杀因为已经移动一次，队友不可能在1号房间，要么暗杀2，要么暗杀3，均是1/2的概率，则需要再第三次暗杀 此时需要3个手榴弹才能保证将队友暗杀 第3种方案 第一次暗杀第3个房间，如果队友在第3个房间则暗杀成功，如果没有则可能位于1、2房间，此时队友爆炸移动后可能位于2、3房间 第二次暗杀因为已经移动一次，队友不可能在1号房间，要么暗杀2，要么暗杀3，均是1/2的概率，则需要再第三次暗杀 此时需要3个手榴弹才能保证将队友暗杀 从以上三种方案得出在100%的方案下，第一种消耗的手榴弹最少，故为2