Balans

To zadanie pochodzi z Codeforces. Tam też znajdują się testy do zadania.
Jeśli Twoje rozwiązanie zostanie pozytywnie ocenione na tamtych testach, należy wysłać tu zgłoszenie wypisujące "Zrobione".

Limit pamięci: 256MB

Chcemy przejść przez drzwi, których pilnuje strażnik. Stażnik posiada pewien napis długości n.
Gdy sprawdza dostęp, prosi o klucz (również będący napisem).
Następnie wybiera pewien sufiks, a długość najdłuższego wspólnego prefiksu sufiksu i klucza oznacza przez l.
Wtedy l jest współczynnikiem szans na wpuszczeniem do środka.
Zdobyliśmy tajny klucz strażnika i chcemy również wybrać jakiś jego sufiks za nasz klucz.
Jednak skoro nie wiemy jaki sufiks wybierze strażnik, przypiszemy każdemu sufiksowi prawdopodobieństwo z jakim go wybierzemy.
Chcemy zmaksymalizować minimalną wartość oczekiwaną l dla wszystkich możliwych sufiksów.
Oblicz ją. (dokładniejsze wyjaśnienie wartości jaką chcemy obliczyć w oryginalnej treści)

Wejście

W pierwszym wierszy znajduje się liczba całkowita T (T<=10) oznaczająca liczba przypadków testowych.
W następnych T wierszach podane jest T napisów oznaczających klucze strażnika w kolejnych testach.
Długość każdego napisu nie przekracza 2*105, zaś suma długości - 5*105.

Wyjście

Na wyjście dla każdego testu wypisz szukaną wartość.
Odpowiedź zostanie zaakceptowana, jeśli błąd względny i bezwzględny nie przekroczy 10-9.

Przykład

Wejście:
3
aba
aaaaaaaaaaa
abcd


Wyjscie:
0.66666666667
1
0.48