Just So You Know

Matthew는 지혜로운 사람이고 Jesse는 그의 가장 친한 친구입니다. 어느 날 Jesse가 길이 n인 정수 수열 A를 Matthew에게 주고, A의 연속된 부분 수열 B를 하나 골라 비밀로 표시했습니다. Matthew는 처음에 B를 모르지만, 추측을 통해 B를 알아낼 수 있습니다. Matthew가 추측을 하나 제시하면 Jesse가 그 추측이 참인지 거짓인지 즉시 알려 줍니다. B는 A에서 같은 확률로 고른 구간입니다. 지혜로운 사람은 혼란스러워하지 않으므로, Matthew는 B를 알아내는 데 필요한 추측 횟수의 기댓값을 최소화합니다. 그 기댓값을 구해 주세요. 답은 기약분수 p/q(p와 q는 서로소)로 나타냅니다.

첫 줄에 테스트 케이스의 수 T가 주어집니다. 이어서 각 테스트 케이스가 주어집니다. 각 테스트 케이스의 첫 줄에는 정수 n이, 둘째 줄에는 공백으로 구분된 정수 A_1, A_2, ..., A_n이 주어집니다. 제약 조건은 $1 \le T \le 1000$, $1 \le n \le 10^6$, $i = 1, 2, \dots, n$에 대해 $0 \le A_i < 100$입니다. 모든 테스트 케이스의 n 합은 $10^7$을 넘지 않으며, 표준 입력 파일의 크기는 24 MiB를 넘지 않습니다.

각 테스트 케이스마다 답을 한 줄에 출력합니다. q가 1이 아니면 기약분수 p/q로, q가 1이면 정수 p로 출력합니다.

두 번째 예제에 대한 최선의 풀이 중 하나는 먼저 추측 1을 제시하고, 나머지는 결과에 따라 순서대로 제시하는 것입니다.

• 추측 1: B에 포함된 1의 개수가 홀수이다. 참이면 추측 2로, 거짓이면 추측 3으로 갑니다.
• 추측 2: B의 길이가 1이다. 참이면 B는 [1]이고, 거짓이면 추측 4로 갑니다.
• 추측 3: B의 첫 번째 원소가 1이다. 참이면 추측 5로, 거짓이면 추측 6으로 갑니다.
• 추측 4: B의 길이가 4이다. 참이면 B는 [1, 2, 1, 1]이고, 거짓이면 추측 7로 갑니다.
• 추측 5: B의 길이가 3이다. 참이면 B는 [1, 2, 1]이고, 거짓이면 B는 [1, 1]입니다.
• 추측 6: B의 길이가 1이다. 참이면 B는 [2]이고, 거짓이면 B는 [2, 1, 1]입니다.
• 추측 7: B의 첫 번째 원소가 1이다. 참이면 B는 [1, 2]이고, 거짓이면 B는 [2, 1]입니다.