Mihai are un şir de caractere de lungime **N** format din litere mici şi mari ale alfabetului Englez şi cifre. Acesta definieşte un substring (e.g. caractere aflate pe poziţii consecutive) ca fiind duplicat, dacă substring-ul apare de cel putin 2 ori in şirul iniţial, la poziţii diferite. Mai mult, Mihai defineşte valoarea unui şir de caractere astfel: probabilitatea ca alegând aleator un substring nevid, acesta să fie duplicat. Să se găsească valoarea unui şir de caractere dat. Rezultatul se va afişa sub forma unei fracţii **ireductibile**.

Când Mihai alege aleator un substring nevid acesta procedează astfel: alege 2 poziţii (start, end) aleator din mulţimea <tex>\{(i, j) | 1 <= i <= j <= N\}</tex>iar substringul ales este cel aflat între poziţiile *start* şi *end* (considerând indexare de la *1* la *N*).

Precizare: Când Mihai alege aleator un substring nevid acesta procedează astfel: alege 2 poziţii (start, end) aleator din mulţimea <tex>\{(i, j) | 1 <= i <= j <= N\}</tex>iar substringul ales este cel aflat între poziţiile *start* şi *end* (considerând indexare de la *1* la *N*).

h2. Date de intrare

* $ 1 ≤ T ≤ 5 $
* $ 1 ≤ N ≤ 1500 $

* Când Mihai alege aleator un substring nevid acesta procedează astfel:

h2. Exemplu