E. Rating Recalculating
time limit per test
0.25 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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 $$$\leqslant$$$ 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 \geqslant 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 = $$$int(1/f) - 1$$$, where $$$int(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$$$.

Input

First line contains $$$T, 1 \leqslant T \leqslant 20$$$ — number of testcases. Each of the following $$$T$$$ lines contains a single integer number $$$r$$$ — Adamant's rating, $$$5 \leqslant r \leqslant 4000$$$.

Output

On each of the $$$T$$$ lines a single integer $$$k \geqslant 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.

Examples
Input
1
5
Output
2
Input
2
100
200
Output
5
7
Input
3
2500
3000
3500
Output
23
25
27
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. $$$$$$