Substring Draw

The sidewalk in front of the school is once again buried under fallen leaves, and this week's monitors, Hektor and Wiktor, have to rake them. To decide who does it, the two boys agree on an unusual draw.

First they pick a single word made of $N$ lowercase English letters. Then they drop every non-empty substring of that word into an urn, counting each substring once per position at which it occurs. In other words, if a substring appears at $k$ different positions, then $k$ slips carrying that string go into the urn. A word of length $N$ therefore contributes exactly $\frac{N(N+1)}{2}$ slips.

Hektor draws one slip first, then Wiktor draws one of the remaining slips (without replacement). Comparing the two drawn strings lexicographically, whoever drew the smaller string rakes the leaves. If the two drawn strings are equal, they split the sidewalk in half.

What is the probability that the draw ends in a tie, that is, that the two drawn strings are equal?

The first line contains the number of test sets $Z$ ($1 \le Z \le 10$).

Each test set follows in order. The first line of a test set contains the word length $N$ ($2 \le N \le 50\,000$), and the second line contains the word of length $N$ made of lowercase English letters.

For each test set, print the tie probability on its own line as an irreducible fraction. The format is numerator / denominator, where numerator and denominator are coprime and a single space surrounds the slash. When the probability is $0$, print 0 / 1.

Consider the word aaa. Counted by position, it has exactly 6 substrings: a (positions 1..1), aa (positions 1..2), aaa (positions 1..3), a (positions 2..2), aa (positions 2..3), a (positions 3..3). There are $6 \times 5 = 30$ ordered ways to draw two different slips, and 8 of them draw equal strings: (1,4), (1,6), (4,1), (4,6), (6,1), (6,4), (2,5), (5,2) (in each pair the first number is Hektor's slip and the second is Wiktor's). So the tie probability is $\frac{8}{30} = \frac{4}{15}$.