原根

题目描述

回答$T$组询问，每次给一个素数$p$，输出它最小的原根$g$。

输入格式

第一行一个整数$T$。接下来$T$行，每行一个整数表示数字$p$。

输出格式

一个整数，表示最小的原根。

样例输入

3
2
178187
998244353

样例输出

1
2
3

数据范围

对于所有数据，保证$T\leq 100$，保证$2\leq p\leq 10^9$，并且$p$是素数。