Person in Charge

• 035966_L3

Attention

is the hard version of this problem.

This problem requires file I/O (factorial.in / factorial.out).

Problem Background

The lottery results are out. Sleeping Dolphin was surprised to find that he didn't win because... he accidentally bought a different lottery ticket.

Sleeping Dolphin checked his phone—it was already 1:00 AM on April 13th.

Time to focus on setting problems for Sleeping Cup. Let's get to work.

Problem Description

Find the maximum positive integer solution $x$ to the following equation:

where $x! = 1 \times 2 \times \ldots \times x$.

If no such positive integer solution exists, output $0$.

Input Format

There are multiple test cases.

The first line contains a positive integer $T\ (1 \le T \le 1000)$ indicating the number of test cases.

Each of the next $T$ lines contains a positive integer $n\ (1 \le n \le 10^9)$.

Output Format

Output $T$ lines, each containing a non-negative integer representing the answer.

Samples

5
1
2
3
4
5

0
1
1
1
3

5
118
119
120
121
122

1
5
1
9
1

Sample 1 Explanation

From the red-marked parts in the table above, the answers for the sample are $0,1,1,1,3$.

Note that when $n=1$, the equation has infinitely many positive integer solutions ($1 \bmod 1 = 0$), so the answer is $0$.

Official Solution

link