题目描述

你有一个排列长度为 $n(n\le10^{18})$ 的排列 $A$，初始 $A_i=i$，现在对它进行一次 $\mathrm{shuffle}(1,n)$ 操作。$\mathrm{shuffle}(L,R)$ 的定义如下：

• $R\ =\ L\ +\ 1$ 时，$\mathrm{swap}(A_L,A_R)$
• 否则，依次执行 $\mathrm{shuffle}(L,R-1)$, $\mathrm{shuffle}(L+1,R)$

您需要求出 $\mathrm{shuffle}(1,\ n)$ 执行完毕后，$A_k (1\le k\le n)$ 的值。共 $T$ 组数据。