题目描述

一句话题意：

定义 $a_0=1,a_n=2^{a_{n-1}}$，可以证明 $b_n=a_n\bmod p$ 在某一项后都是同一个值，求这个值。

即求解

输入格式

第一行一个整数 $T$，表示数据个数。

接下来 $T$ 行，每行一个正整数 $p$，代表你需要取模的值。

输出格式

$T$ 行，每行一个正整数，为答案对 $p$ 取模后的值。

3
2
3
6

0
1
4

提示

对于 $100\%$ 的数据，$T\le 10^3$，$p\le10^7$。