{"raw_statement":[{"iden":"statement","content":"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.\n\nWhen 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.\n\nAn 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:\n\nFirst, 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$.\n\nMike 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.\n\nBased on the given Adamant rating, find the minimum $k$ so that the described algorithm assigns him a division strictly greater than $1$.\n\nFirst 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$.\n\nOn 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.\n\nAs usual, $e = 2. 718281828459045 \\\\dots$ — Euler constant.\n\nThe 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. $$\n\n"},{"iden":"input","content":"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$."},{"iden":"output","content":"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."},{"iden":"examples","content":"Input1\n5\nOutput2\nInput2\n100\n200\nOutput5\n7\nInput3\n2500\n3000\n3500\nOutput23\n25\n27\n"},{"iden":"note","content":"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. $$"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ e \\approx 2.718281828459045 $ be the Euler constant.  \nFor integers $ n \\geq 0 $ and real $ x $, define:  \n$$\nf(n, x) = \\frac{1}{e^x} \\sum_{i=0}^{n} \\frac{x^i}{i!}\n$$\n\n**Given**  \nLet $ r \\in \\mathbb{Z} $ be Adamant’s rating, with $ 5 \\leq r \\leq 4000 $.  \nLet $ k \\in \\mathbb{Z}^+ $ be a parameter. Define:  \n$$\nf_k = f(k, r - k) = \\frac{1}{e^{r - k}} \\sum_{i=0}^{k} \\frac{(r - k)^i}{i!}\n$$  \nThe division is computed as:  \n$$\n\\text{div} = \\left\\lfloor \\frac{1}{f_k} \\right\\rfloor - 1\n$$\n\n**Objective**  \nFor each test case, find the **minimum** $ k \\geq 1 $ such that:  \n$$\n\\left\\lfloor \\frac{1}{f_k} \\right\\rfloor - 1 > 1\n\\quad \\Leftrightarrow \\quad\n\\left\\lfloor \\frac{1}{f_k} \\right\\rfloor \\geq 3\n\\quad \\Leftrightarrow \\quad\n\\frac{1}{f_k} \\geq 3\n\\quad \\Leftrightarrow \\quad\nf_k \\leq \\frac{1}{3}\n$$","simple_statement":"Given Adamant’s rating $ r $, find the smallest positive integer $ k $ such that when you compute:\n\n$$\nf = \\frac{1 + (r - k) + \\frac{(r - k)^2}{2!} + \\dots + \\frac{(r - k)^{r - k}}{(r - k)!}}{e^{r - k}}\n$$\n\nand then set $ \\text{div} = \\lfloor 1 / f \\rfloor - 1 $, the result is **strictly greater than 1**.\n\nYou need to find the minimum $ k > 0 $ that makes this happen.","has_page_source":false}