철학적 균형

어떤 힘이 리카를 부추겨 LCR을 세우게 했다. LCR이 리카를 EC Final 개최교 부속 중학교로 데려간 것은 우연일까?

리카는 NWPU에 들어가려 하지만, 악마에게 들린 경비원이 그녀를 들여보내 주지 않는다. 그래서 그녀는 출입증을 위조할 생각을 한다.

핵심은 출입증 ID, 즉 접근 핸드셰이킹을 위한 특별한 문자열이다. 경비원은 비밀 키로 길이 $n$의 문자열 $s$를 가지고 있고, 출입증을 검사할 때 그 문자열의 접미사(마지막 문자를 포함하는 부분 문자열) 하나를 골라 출입증 ID와 그 접미사의 최장 공통 접두사의 길이 $l$을 계산한다. $l$은 그녀를 통과시켜 줄 확률에 비례한다.

이제 리카는 어떤 비밀스러운 방법으로 비밀 키를 손에 넣었다. 그녀도 출입증 ID로 접미사 하나를 고르려고 한다. 경비원이 어떤 접미사를 고를지 알 수 없으므로, 리카는 출입증 ID를 무작위로 고르기로 한다. 즉, 리카는 접미사에 대한 확률분포(실수열 $\{p_i\}, i = 1, 2, \dots, n$로, $p_i \ge 0$, $\sum_{i=1}^n p_i = 1$이며, 길이 $i$인 접미사 $s_i$를 확률 $p_i$로 고른다는 뜻)를 설계하고, 경비원이 어떤 접미사를 고르더라도 $l$의 수학적 기댓값이 최소가 되는 경우를 최대화하려 한다.

$l$의 수학적 기댓값의 최솟값이 가질 수 있는 최댓값을 계산할 수 있는가? 정확히 말해, 계산해야 하는 값은 $\max_{\{p_i\}} \left(\min_{j=1}^n\left(\sum_{k=1}^n p_k \mathrm{lcp}(s_k,s_j)\right)\right)$이며, 여기서 $\mathrm{lcp}(s_k,s_j)$는 $s_k$와 $s_j$의 최장 공통 접두사의 길이를 뜻한다.

첫 줄에는 테스트 케이스의 수 $T (1 \leq T \leq 10^5)$가 주어진다. 이어서 $T$개의 테스트 케이스가 주어진다.

각 테스트 케이스에는 소문자로만 이루어진 길이 $n (1 \leq n \leq 2 \times 10^5)$의 문자열 $s$, 즉 비밀 키가 주어진다.

모든 테스트 케이스에서 $n$의 합은 $5 \times 10^5$ 이하이다.

출력은 $T$줄이고, 각 줄에는 해당 테스트 케이스의 답을 소수로 출력한다.

절대 오차 또는 상대 오차가 $10^{-9}$를 넘지 않으면 정답으로 인정된다.