Bob prepared $n+1$ coins as New Year's lucky money to give to Alice. To make it more interesting, they decided to play a game:

At the beginning of the game, Bob gives $1$ coin to Alice. At this time, Alice has $1$ coin, and Bob has $n$ coins.

Next, Alice can repeatedly perform the following operation until she has taken all of Bob's coins:

• Suppose Alice currently has $A$ coins and Bob has $B$ coins. Alice can choose a positive integer $k$ satisfying $1 \le k \le \gcd(A, B)$, and transfer $k$ coins from Bob's hand to her own.

Here, $\gcd(A, B)$ denotes the greatest common divisor of $A$ and $B$.

What is the minimum number of operations Alice needs to take all of Bob's coins?

Input

The first line contains an integer $T$ ($1 \le T \le 3 \times 10^3$), denoting the number of test cases.

The next $T$ lines each contain an integer $n$ ($1 \le n \le 10^9$).

Output

Output $T$ lines. Each line contains an integer representing the minimum number of operations for the corresponding test case.

Examples

Input 1

2
5
9

Output 1

3
4

Note

First test case ($n = 5$, Bob initially has 5 coins):

1. Initially Alice has 1 coin, Bob has 5. $\gcd(1, 5) = 1$, take $k = 1$. Alice's coins become $2$, Bob has $4$ left.
2. $\gcd(2, 4) = 2$, take $k = 2$. Alice's coins become $4$, Bob has $2$ left.
3. $\gcd(4, 2) = 2$, take $k = 2$. Alice's coins become $6$, Bob has $0$ left.

During the transfers, Alice's coin count changes as: $1 \to 2 \to 4 \to 6$, requiring $3$ steps in total.

Second test case ($n = 9$, Bob initially has 9 coins):

During the transfers, Alice's coin count changes as: $1 \to 2 \to 4 \to 5 \to 10$.

It requires $4$ steps.