부분 문자열 제비뽑기

학교 앞 인도가 또다시 낙엽으로 뒤덮였습니다. 이번 주 당번인 헥토르와 빅토르는 낙엽을 쓸어야 합니다. 누가 치울지 정하기 위해 두 사람은 조금 특이한 제비뽑기를 하기로 했습니다.

먼저 소문자 영어 알파벳 $N$개로 이루어진 단어 하나를 함께 정합니다. 그런 다음 이 단어의 모든 비어 있지 않은 부분 문자열을 항아리에 넣습니다. 이때 부분 문자열은 나타나는 위치마다 따로 셉니다. 즉 어떤 부분 문자열이 서로 다른 $k$개의 위치에서 등장하면 그 문자열이 적힌 쪽지를 $k$장 넣습니다. 따라서 길이 $N$인 단어에서는 정확히 $\frac{N(N+1)}{2}$장의 쪽지가 항아리에 들어갑니다.

이제 헥토르가 먼저 쪽지 한 장을 뽑고, 이어서 빅토르가 남은 쪽지 중에서 한 장을 뽑습니다(되돌려 넣지 않음). 두 쪽지에 적힌 문자열을 사전순으로 비교하여, 더 작은 문자열을 뽑은 사람이 낙엽을 쓸게 됩니다. 만약 두 사람이 뽑은 문자열이 서로 같으면 인도를 절반씩 나누어 쓸게 됩니다.

두 사람이 뽑은 문자열이 같아서 비기게 될 확률은 얼마일까요?

첫 번째 줄에 테스트 세트의 개수 $Z$ ($1 \le Z \le 10$)가 주어집니다.

이어서 각 테스트 세트가 순서대로 주어집니다. 각 테스트 세트의 첫 번째 줄에는 단어의 길이 $N$ ($2 \le N \le 50\,000$)이 주어지고, 두 번째 줄에는 소문자 영어 알파벳으로 이루어진 길이 $N$의 단어가 주어집니다.

각 테스트 세트마다, 비길 확률을 기약분수 형태로 한 줄에 출력합니다. 출력 형식은 분자 / 분모이며, 분자와 분모는 서로소이고 슬래시 양옆에 공백이 하나씩 있습니다. 확률이 $0$일 때는 0 / 1로 출력합니다.

단어가 aaa인 경우를 살펴봅시다. 위치마다 세면 부분 문자열은 정확히 6장입니다: a (위치 1..1), aa (위치 1..2), aaa (위치 1..3), a (위치 2..2), aa (위치 2..3), a (위치 3..3). 서로 다른 두 장을 순서대로 뽑는 경우의 수는 $6 \times 5 = 30$가지이고, 그중 두 문자열이 같아 비기는 경우는 8가지입니다: (1,4), (1,6), (4,1), (4,6), (6,1), (6,4), (2,5), (5,2) (각 쌍의 첫 번째 수는 헥토르가 뽑은 쪽지 번호, 두 번째 수는 빅토르가 뽑은 쪽지 번호입니다). 따라서 비길 확률은 $\frac{8}{30} = \frac{4}{15}$입니다.