7090：银河清浅夜纵横

$\quad\quad$一只小独角兽掌管着一片 $n\times n$ 的夜空，四个顶点分别位于东西南北（图中上北下南）。小独角兽在它的日记本里把这片夜空分成 $1\times 1$ 的小块，每天夜幕降临前，小独角兽会选择其中的一些格子，用它的魔法各放上一颗星星。然后，它会从北顶点出发，沿着网格线飞往南顶点，顺路观测它放置的星星。小独角兽所经之处将浮现一道星河。
$\quad\quad$布星消耗了太多的魔法，所以小独角兽总是走最短路，并且星星都在星河同一侧——否则，小独角兽就需要不断地左右转动脑袋，然后就转晕了！在路线的每一条线段（单位正方形的边）上，小独角兽会沿着垂直线段的方向望去，然后记录这条线段的垂直方向上是否有星星、如果有看到的是哪颗（如果两颗星星所在的格子都在观测方向上，则后面的星星会被挡住。在小独角兽眼里，每颗星星都是不同的）。如果在两条相互垂直线段上的观测都被记录了看到同一颗星星，则小独角兽认为两个方向的交点上确实放好了这颗星星。小独角兽希望夜空亮一些，这样地上的小生灵们晚上就不会迷路了，所以它总是会放上尽量多的星星，但要保证由观测星星的记录得到的星星位置布局是正确的。



$\quad\quad$小独角兽希望地上的小生灵们每天看到的星空都不同（地上的小生灵无法区分不同的星星），它最多能让连续多少个夜晚的星空（布星位置和星河路线）不重复呢？小独角兽历经千辛万苦，终于算出了答案，并用二进制写在了纸上。不料，小独角兽的好朋友萤火虫来找它玩儿时不小心把这张纸烧着了。火熄灭后，最后64位已经化为灰烬。小独角兽不想重新再算一遍了！你能帮它算出最后64位吗？

简要题意：在 $n\times n$ 的网格里放星星，再画一条从北顶点到南顶点的沿着网格的最短路，使得星星都在同一侧。对于任意一条属于此最短路的单位正方形的边，与此边垂直的一排方格上的第一颗星星（即离此边最近的一颗）可被观测记录，一颗星星在两个垂直方向被记录则能够确定它的位置（每颗星星都不同）。在确保所有星星的位置都能被确定的条件下，取所有符合条件的格局（布星位置（此时视所有星星相同）+一条最短路线）中放星星数量最多的所有格局，输出格局数的二进制最后64位。

$T$ 组数据。

第一行一个正整数 $T\,(1 \le T \le 400)$，表示数据组数。

对于每组数据：

每行一个正整数 $n\,(1\le n \le 10^{18})$，表示小独角兽掌管的夜空大小为 $n\times n$。

对于每组数据：

输出一个 64 位的二进制数，表示答案。