法法

题号：NC19430
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

设 A 是一个 $1 \sim n$ 的排列，其中第 i 项为 A_i

设 $f(A)=A_1^{A_2^{A_3 ^ {\cdots ^ {A_n}}}}$

换句话说：
$f(\{A_1,A_2,A_3, \dots , A_n\}) =\begin{cases} A_1 & n=1 \\ A_1^{f(\{A_2,A_3, \dots , A_n\})} & n > 1 \end{cases}$

求 $1 \sim n$ 的全排列的 f 的和

答案对 2 取模

输入描述:

第一行输入一个整数 T，表示数据组数
之后 T 行，第 i+1 行有一个整数 n_i，表示第 i 次询问

输出描述:

一共 T 行，第 i 行有 1 个整数，表示第 i 次询问的答案

示例1

输入

复制

1
3

输出

复制

说明

备注:

数据范围
1 ≤ n ≤ 10¹⁸
1 ≤ T ≤ 10