{"raw_statement":[{"iden":"statement","content":"*Bakkar* is now a senior college student studying computer science. And as many students; *Bakkar* fell in love with one of his finest colleagues *Maymona*. And as *Bakkar* has no brothers he is counting on getting an exemption from the military service after graduation. He got engaged to *Maymona* in their senior year counting on the exemption and a job he will get after graduation at the same place where he was interning last summer.\n\nWell, man does not always get what he wants; the neither planned nor expected happened. *Bakkar*’s mother is pregnant and will give birth to *Hareedy* before *Bakkar* can get his exemption.\n\n*Hareedy* is now born and unfortunately *Bakkar* will have to postpone his job and marriage plans for a year as he will serve as a military soldier for one year.\n\nOn the first 45 days, soldiers are trained in the military training center. They have to do a variety of exercises daily. One day *Bakkar* woke up late and didn't appear in the morning lineup at time. His commander is now angry and is going to punish him.\n\n*Bakkar* is required to perform push-ups (the push-up position is called 6 esta'ed). His commander tells him to do them in reps (consecutive times) and then rest in between them. The commander wants him to follow a strict pattern. Given an upper limit, he will perform reps with increasing number of push-ups (1, 2, 3, ...) to warm up, until he reaches the upper limit. After that, he starts decreasing the number of push-ups per rep until he stops completely (..., 3, 2, 1). After resting, he will repeat the process again but with a higher upper limit. The upper limit starts with 1, and increases each time by a value of 1.\n\nHere are the first 16 reps:\n\n1\n\n1 2 1\n\n1 2 3 2 1\n\n1 2 3 4 3 2 1 ....\n\nThe total number of push-ups he does is the sum of all the reps has has done so far. So for example, the total number of push-ups after completing 4 reps = 1+1+2+1 = 5, and after completing 7 reps = 1+1+2+1+1+2+3 = 11.\n\n*Bakkar* now has to do at least *N* push-ups. This is very exhausting so he needs to know the minimum number of reps to complete using this pattern to reach his punishment reps.\n\nYour program will be tested on one or more test cases. The first line of the input will be a single integer *T*, the number of test cases (1  ≤  *T*  ≤  100,000). Followed by *T* test cases, each test case will be a single integer *N*, the number of push-ups *Bakkar* wants to perform (1  ≤  *N*  ≤  1018).\n\nFor each test case print a single line containing \"Case n:\" (without the quotes) where n is the test case number (starting from 1) followed by a single space, then a single integer representing the minimum number of reps needed as described above.\n\n"},{"iden":"input","content":"Your program will be tested on one or more test cases. The first line of the input will be a single integer *T*, the number of test cases (1  ≤  *T*  ≤  100,000). Followed by *T* test cases, each test case will be a single integer *N*, the number of push-ups *Bakkar* wants to perform (1  ≤  *N*  ≤  1018)."},{"iden":"output","content":"For each test case print a single line containing \"Case n:\" (without the quotes) where n is the test case number (starting from 1) followed by a single space, then a single integer representing the minimum number of reps needed as described above."},{"iden":"examples","content":"Input569112135OutputCase 1: 5Case 2: 7Case 3: 7Case 4: 13Case 5: 19"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ T \\in \\mathbb{Z}^+ $ be the number of test cases.  \nFor each test case $ k \\in \\{1, \\dots, T\\} $, let $ N_k \\in \\mathbb{Z}^+ $ be the target number of push-ups.\n\nThe push-up sequence is generated in blocks:  \nFor $ m = 1, 2, 3, \\dots $, the $ m $-th block consists of the sequence:  \n$$\n1, 2, 3, \\dots, m, m-1, \\dots, 2, 1\n$$  \nwhich has length $ 2m - 1 $ and sum $ m^2 $.\n\nLet $ S(m) = \\sum_{i=1}^{m} i^2 = \\frac{m(m+1)(2m+1)}{6} $ be the total push-ups after completing $ m $ full blocks.\n\nLet $ R(m) = \\sum_{i=1}^{m} (2i - 1) = m^2 $ be the total number of reps after $ m $ full blocks.\n\n**Constraints**  \n1. $ 1 \\le T \\le 100000 $  \n2. $ 1 \\le N_k \\le 10^{18} $ for each $ k $\n\n**Objective**  \nFor each test case $ k $, find the minimum number of reps $ r $ such that the cumulative sum of push-ups $ \\ge N_k $, where reps follow the block pattern above.\n\nThat is, find the smallest $ r \\in \\mathbb{Z}^+ $ such that there exists an integer $ m \\ge 0 $ and an integer $ j \\in \\{1, \\dots, 2m+1\\} $ (if $ m \\ge 1 $) satisfying:  \n- If $ r = R(m) $, then total push-ups = $ S(m) $.  \n- If $ r = R(m) + j $ with $ j \\le 2m+1 $, then total push-ups = $ S(m) + \\sum_{i=1}^{j} a_i $, where $ a_i = \\min(i, 2m+2 - i) $ is the $ i $-th element of the $ (m+1) $-th block.\n\nEquivalently, find the minimal $ r $ such that the cumulative sum $ \\ge N_k $, computed by:  \n- Find maximal $ m $ such that $ S(m) \\le N_k $.  \n- Then find minimal $ j \\in \\{1, \\dots, 2m+1\\} $ such that $ S(m) + \\sum_{i=1}^{j} \\min(i, 2m+2 - i) \\ge N_k $.  \n- Return $ r = R(m) + j $.\n\nIf $ N_k = 1 $, then $ m = 0 $, $ j = 1 $, $ r = 1 $.","simple_statement":"Bakkar must do push-ups in a pattern:  \nStart with 1, increase to a max, then decrease back to 1.  \nThen repeat with max increased by 1.  \n\nPattern:  \nRep 1: 1  \nRep 2: 1 2 1  \nRep 3: 1 2 3 2 1  \nRep 4: 1 2 3 4 3 2 1  \n...  \n\nEach \"rep\" here is one full up-down sequence.  \nTotal push-ups = sum of all numbers in all reps done so far.  \n\nGiven N, find the minimum number of reps needed so that total push-ups ≥ N.","has_page_source":false}