负责人

• 035966_L3

注意

本题有加强版：P129

本题需要文件读写（factorial.in / factorial.out）。

题目背景

彩票的开奖结果出来了。Sleeping Dolphin 惊讶地发现自己没有中奖，因为……它不小心买了另一种彩票。

Sleeping Dolphin 掏出手机一看——现在已经是 $4$ 月 $13$ 日凌晨 $1$ 点了。

还是给 Sleeping Cup 出题要紧。开始办正事吧。

题目描述

求以下关于 $x$ 的方程的最大正整数解：

$$x! \equiv 1\ (\bmod\ n)$$

其中 $x!=1\times2\times\ldots\times x$。

如果最大正整数解不存在，那么输出 $0$。

输入格式

本题有多组数据。

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

下面 $T$ 行，每行一个正整数 $n$。

输出格式

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

样例

5
1
2
3
4
5

0
1
1
1
3

5
118
119
120
121
122

1
5
1
9
1

样例 1 解释

$\color{blue}\#$	$\color{blue}1!\ (=1)$	$\color{blue}2!\ (=2)$	$\color{blue}3!\ (=6)$	$\color{blue}4!\ (=24)$	$\color{blue}5!\ (=120)$	$\color{blue}\ldots$
$\color{blue}\bmod\ 1$	$\color{red}=0$	$\color{red}=0$	$\color{red}=0$	$\color{red}=0$	$\color{red}=0$	$\color{red}=0$
$\color{blue}\bmod\ 2$	$\color{red}=1$	$=0$	$=0$	$=0$	$=0$	$=0$
$\color{blue}\bmod\ 3$	$\color{red}=1$	$=2$	$=0$	$=0$	$=0$	$=0$
$\color{blue}\bmod\ 4$	$\color{red}=1$	$=2$	$=2$	$=0$	$=0$	$=0$
$\color{blue}\bmod\ 5$	$\color{red}=1$	$=2$	$\color{red}=1$	$=4$	$=0$	$=0$

由上表标红的部分可知，样例的答案为 $0,1,1,1,3$。

特别地，$n=1$ 时方程存在无穷多组正整数解（$1\bmod 1=0$），此时的答案为 $0$。

数据范围

对于 $100\%$ 的数据，$1 \le T \le 1000$，$1 \le n \le 10^9$。

官方题解

link