上帝与集合的正确用法

题目来源

BZOJ 3884

题目描述

给定一个数字$p$，求$$2^{2^{2^{\dots}}} \bmod p$$的值。

输入格式

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

接下来$T$行，每行一个整数$p$。

输出格式

一共$T$行，每行一个整数，表示答案。

样例输入

3
2
3
6

样例输出

0
1
4

数据范围

对于所有的数据，保证$1\leq T\leq 1000, 1\leq p \leq 10^7$。