某种力量影响了 Rikka，让她放了 LCR 的鸽子。LCR 把她带到 EC Final 主办方附属的中学，这难道是巧合吗？

Rikka 试图进入 NWPU，但被恶魔附身的守卫拦住了。现在她想到了一个伪造通行证的主意。

关键在于通行证 ID，这是一个用于访问握手的特殊字符串。守卫拥有一个长度为 $n$ 的字符串 $s$ 作为密钥；当他检查通行证时，他会从中选择一个后缀（即包含最后一个字符的子串），并计算通行证 ID 与该后缀的最长公共前缀长度 $l$。$l$ 与她通过的概率成正比。

现在 Rikka 通过某种秘密途径获得了密钥。她也想选择一个后缀作为通行证 ID。由于守卫会选择哪个后缀是未知的，Rikka 将随机选择她的通行证 ID。也就是说，Rikka 会为后缀设计一个概率分布（即一系列实数 $\{p_i\}, i = 1, 2, \dots, n$，满足 $p_i \ge 0, \sum_{i=1}^n p_i = 1$，这意味着她会以 $p_i$ 的概率选择长度为 $i$ 的后缀，记为 $s_i$），并最大化守卫选择任意后缀时 $l$ 的最小数学期望。

请你计算这个最小数学期望的最大值。准确地说，你需要计算的是：

$$\max_{\{p_i\}} \left( \min_{j=1}^n \left( \sum_{k=1}^n p_k \text{lcp}(s_k, s_j) \right) \right)$$

其中 $\text{lcp}(s_k, s_j)$ 表示 $s_k$ 和 $s_j$ 的最长公共前缀长度。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 10^5$)，表示测试用例的数量。接下来是 $T$ 个测试用例。 每个测试用例包含一个长度为 $n$ ($1 \le n \le 2 \times 10^5$) 的字符串 $s$，仅由小写字母组成，即密钥。 保证所有测试用例中 $n$ 的总和不超过 $5 \times 10^5$。

输出格式

输出 $T$ 行；每行包含一个十进制数，即该测试用例的答案。 如果你的答案与标准答案的绝对误差或相对误差不超过 $10^{-9}$，则视为正确。

样例

输入 1

3
aba
aaaaaaaaaaa
abcd

输出 1

0.66666666667
1
0.48