It is well known that the border for red color on CF is designed to pass right above Adamant's rating. However, recently, due to an internal error in rating recalculation algorithms Adamant finally became red.
When it happened, Mike realized the algorithm should be fixed urgently. To solve this issue once and for all, we want to design a new division system, so that Adamant goes to div 2 and would be far from red color.
An obvious solution would be to simply put a line _if rating $<=.slant$ adamant.rating then div = max (div, 2)_ into the existing system, but this would look very suspicious. So Mike came up with the following, rather intricate, procedure:
First, Mike selects the integer parameter $k >=.slant 0$. Then, he calculates the value of the function $f = f (r -k, r)$, where $r$ is the user's rating, and $$ f(n, x) := (1 + x + x^2/2! + x^3/3! + \dots + x^n/n!)/e^x. $$ Finally, the user's division is defined by the formula div = $i n t (1 \/ f) -1$, where $i n t (x)$ returns maximal integer not exceeding $x$.
Mike is sure that due to the introduction of div 3 and div 4 to the platform, such a function will be more fair not only to Adamant, but also to all users in general.
Based on the given Adamant rating, find the minimum $k$ so that the described algorithm assigns him a division strictly greater than $1$.
First line contains $T, 1 <=.slant T <=.slant 20$ — number of testcases. Each of the following $T$ lines contains a single integer number $r$ — Adamant's rating, $5 <=.slant r <=.slant 4000$.
On each of the $T$ lines a single integer $k >=.slant 0$ — minimal parameteer so that the described algorithm would produce a number stricly greater than 1. It is guaranteed that such a nonnegative $k$ exists.
As usual, $e = 2. 718281828459045 \\dots$ — Euler constant.
The fraction's numerator contains incomplete Taylor series for the function $e^x$, where the whole series is $$ e^x = 1 + x/1! + x^2/2! + \dots + x^n/n! + \dots. $$
## Input
First line contains $T, 1 <=.slant T <=.slant 20$ — number of testcases. Each of the following $T$ lines contains a single integer number $r$ — Adamant's rating, $5 <=.slant r <=.slant 4000$.
## Output
On each of the $T$ lines a single integer $k >=.slant 0$ — minimal parameteer so that the described algorithm would produce a number stricly greater than 1. It is guaranteed that such a nonnegative $k$ exists.
[samples]
## Note
As usual, $e = 2. 718281828459045 \\dots$ — Euler constant.The fraction's numerator contains incomplete Taylor series for the function $e^x$, where the whole series is $$ e^x = 1 + x/1! + x^2/2! + \dots + x^n/n! + \dots. $$
**Definitions**
Let $ e \approx 2.718281828459045 $ be the Euler constant.
For integers $ n \geq 0 $ and real $ x $, define:
$$
f(n, x) = \frac{1}{e^x} \sum_{i=0}^{n} \frac{x^i}{i!}
$$
**Given**
Let $ r \in \mathbb{Z} $ be Adamant’s rating, with $ 5 \leq r \leq 4000 $.
Let $ k \in \mathbb{Z}^+ $ be a parameter. Define:
$$
f_k = f(k, r - k) = \frac{1}{e^{r - k}} \sum_{i=0}^{k} \frac{(r - k)^i}{i!}
$$
The division is computed as:
$$
\text{div} = \left\lfloor \frac{1}{f_k} \right\rfloor - 1
$$
**Objective**
For each test case, find the **minimum** $ k \geq 1 $ such that:
$$
\left\lfloor \frac{1}{f_k} \right\rfloor - 1 > 1
\quad \Leftrightarrow \quad
\left\lfloor \frac{1}{f_k} \right\rfloor \geq 3
\quad \Leftrightarrow \quad
\frac{1}{f_k} \geq 3
\quad \Leftrightarrow \quad
f_k \leq \frac{1}{3}
$$