{"raw_statement":[{"iden":"statement","content":"Some power influenced Rikka to stand LCR up. Is it a coincidence that LCR brought her to the middle school attached to the EC Final host?\n\nRikka is trying to enter the NWPU, but the guard who has been possessed by the devil doesn't let her in. Now she has an idea of forging a pass.\n\nThe key is the pass ID, a special string for access-handshaking. The guard has a string $s$ of length $n$ as the secret key; when he checks a pass, he chooses a suffix of it (that is, a substring containing the last character), and calculates the length $l$ of the longest common prefix of the pass ID and the suffix. $l$ is proportion to the probability to let her pass.\n\nNow Rikka has got the secret key in some secret way. She wants to choose a suffix as the pass ID, too. Since the suffix which the guard will choose is unknown, Rikka would choose her pass ID randomly. That is, Rikka would design a probability distribution for the suffixes (i.e. a series of real numbers ${p_i}, i = 1, 2, \\\\dots, n$, such that $p_i >= 0, sum_{i = 1}^n p_i = 1$, which means she would choose the suffix of length $i$, denoted by $s_i$, with a probability of $p_i$), and maximize the minimum mathematical expectation of $l$ for any suffix the guard chooses.\n\nCould you please calculate the maximum value of the minimum mathematical expectation of $l$? Precisely speaking, what you should calculate is $$\\max_{\\{p_i\\}} \\left(\\min_{j=1}^n\\left(\\sum_{k=1}^n p_k \\mathrm{lcp}(s_k,s_j)\\right)\\right),$$ where $upright(l c p) (s_k, s_j)$ means the length of longest common prefix of $s_k$ and $s_j$.\n\nThe first line contains one integer $T med (1 <= T <= 10^5)$, the number of test cases. Then $T$ test cases follow.\n\nEach test case contains a string $s$ of length $n med (1 <= n <= 2 times 10^5)$, consisting of only lowercase letters, the secret key.\n\nIt is guaranteed that the sum of $n$ in all test cases is at most $5 times 10^5$.\n\nOutput $T$ lines; each line contains a decimal number, the answer to that test case.\n\nYour answer is considered correct if the absolute or relative error doesn't exceed $10^(-9)$.\n\n"},{"iden":"input","content":"The first line contains one integer $T med (1 <= T <= 10^5)$, the number of test cases. Then $T$ test cases follow.Each test case contains a string $s$ of length $n med (1 <= n <= 2 times 10^5)$, consisting of only lowercase letters, the secret key.It is guaranteed that the sum of $n$ in all test cases is at most $5 times 10^5$."},{"iden":"output","content":"Output $T$ lines; each line contains a decimal number, the answer to that test case.Your answer is considered correct if the absolute or relative error doesn't exceed $10^(-9)$."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ s $ be a string of length $ n $. For $ i \\in \\{1, \\dots, n\\} $, let $ s_i $ denote the suffix of $ s $ starting at position $ i $, i.e., $ s_i = s[i..n] $.  \nLet $ \\mathrm{lcp}(s_i, s_j) $ denote the length of the longest common prefix between suffixes $ s_i $ and $ s_j $.\n\n**Constraints**  \n1. $ 1 \\leq n \\leq 2 \\times 10^5 $  \n2. $ s $ consists only of lowercase English letters.  \n3. The total sum of $ n $ across all test cases is at most $ 5 \\times 10^5 $.  \n\n**Objective**  \nFind  \n$$\n\\max_{\\substack{p_i \\geq 0 \\\\ \\sum_{i=1}^n p_i = 1}} \\left( \\min_{j=1}^n \\sum_{k=1}^n p_k \\cdot \\mathrm{lcp}(s_k, s_j) \\right)\n$$","simple_statement":"Rikka wants to pick a suffix of string s as her pass ID. The guard will randomly pick a suffix and compare its longest common prefix (LCP) with Rikka’s choice. Rikka can choose any probability distribution over the suffixes. She wants to maximize the minimum expected LCP over all possible guard choices. Find that maximum minimum expectation.","has_page_source":false}