已知函数：

unsigned int Hash(unsigned int v)
{
    unsigned int t = v;
    t = t + (t <> 6);
    t = t + (t <> 11);
    t = t + (t << 16);
    return t;
}

的返回值为t，求传入的参数v。

输入格式

第一行包含一个正整数 $Q(1 \le Q \le 10^5)$，表示询问的个数。

接下来 $Q$ 行，每行一个整数 $t(0 \le t < 2^{32})$，表示询问的t。

输入数据保证对于每个 $t$ 至少存在一组解。

输出格式

对于每组数据输出一行一个整数，即合法的 $v$ ，若有多组可行解，输出任意一组。

样例输入

4
614278301
1228622139
1841720774
2457244278

样例输出

1
2
3
4