Just So You Know

Matthew is a wise man, and Jesse is his best friend. One day, Jesse gave Matthew an integer sequence A of length n and privately marked one contiguous subsequence B of A. Matthew does not know B at first, but he can work it out by making conjectures. Each time he makes a conjecture, Jesse immediately tells him whether it is true or false. Matthew knows that B is an interval chosen from A with equal probability. A wise man is never confused, so Matthew minimizes the expected number of conjectures he needs to identify B. Find that expected value. Write the answer as an irreducible fraction p/q, where p and q are coprime.

The first line contains one integer T, the number of test cases. Each test case follows. The first line of a test case contains one integer n. The second line contains n space-separated integers A_1, A_2, ..., A_n. Constraints: $1 \le T \le 1000$, $1 \le n \le 10^6$, $0 \le A_i < 100$ for $i = 1, 2, \dots, n$. The sum of n over all test cases does not exceed $10^7$, and the size of the standard input file does not exceed 24 MiB.

For each test case, print the answer on one line as an irreducible fraction p/q if q is not 1, or as the integer p otherwise.

One possible best solution for the second sample is to make Conjecture 1 first, then make the rest in order based on the answers.

• Conjecture 1: The number of 1s in B is odd. If true, go to Conjecture 2, else go to Conjecture 3.
• Conjecture 2: The length of B is 1. If true, B is [1], else go to Conjecture 4.
• Conjecture 3: The first element of B is 1. If true, go to Conjecture 5, else go to Conjecture 6.
• Conjecture 4: The length of B is 4. If true, B is [1, 2, 1, 1], else go to Conjecture 7.
• Conjecture 5: The length of B is 3. If true, B is [1, 2, 1], else B is [1, 1].
• Conjecture 6: The length of B is 1. If true, B is [2], else B is [2, 1, 1].
• Conjecture 7: The first element of B is 1. If true, B is [1, 2], else B is [2, 1].