Matthew 是一个智者，Jesse 是他最好的朋友。有一天，Jesse 给 Matthew 一个长度为 $n$ 的整数序列 $A$，并私下标记了 $A$ 的一个连续子序列 $B$。起初 Matthew 不知道序列 $B$，但他可以通过猜想来确定该序列。也就是说，一旦他提出某个猜想，Jesse 会立即告诉他该猜想是否正确。

Matthew 知道序列 $B$ 是从序列 $A$ 中等概率选择的一个区间。智者从不困惑，因此 Matthew 将最小化他确定序列 $B$ 所需的期望猜想次数。请你计算这个期望值。你的答案应该是一个既约分数 $p/q$，即 $p$ 和 $q$ 互质。

输入格式

第一行包含一个整数 $T$，表示测试用例的数量。 接下来描述所有的测试用例。对于每个测试用例： 第一行包含一个整数 $n$。 第二行包含 $n$ 个空格分隔的整数 $A_1, A_2, \dots, A_n$。 $1 \le T \le 1000, 1 \le n \le 10^6, 0 \le A_i < 100 (i = 1, 2, \dots, n)$。 保证所有测试用例中 $n$ 的总和不超过 $10^7$，且标准输入文件的大小不超过 $24$ MiB。

输出格式

对于每个测试用例，在一行中输出答案。如果 $q=1$，则输出一个简单的整数 $p$，否则输出既约分数 $p/q$。

样例

输入 1

3
2
1 1
4
1 2 1 1
6
1 1 4 5 1 4

输出 1

1
29/10
85/21

说明

以下是第二个样例的一种可能的最佳方案。首先提出猜想 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]$。