该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

负责人

• 035966_L3

注意

本题有加强版：P129

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

题目背景

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

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

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

题目描述

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

其中 $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 解释

由上表标红的部分可知，样例的答案为 $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