说明

小 L 需要维护一个口袋，口袋里全是数，一开始只有一个数 $1$，口袋中可以有很多数，同一个数可以出现多次。

小 L 对口袋依次进行 $n$ 次操作，总共有三种不同的操作：

1. 第一种操作：往口袋里添加一个新的数，值为 $1$。
2. 第二种操作：取出口袋中两个数 $a$ 和 $b$，这两个数是小 L 自选的，之后将 $a+b$ 这一个数放回这个口袋中，取出的数不放回。
3. 第三种操作：这次操作小 L 可以自由选择为第一种操作或者第二种操作执行。

小 L 每次执行第二种操作的时候，如果当时口袋里的数个数 $<2$，则小 L 会很急。这里如果本来需要执行的是第三种操作，然后小 L 选择了把这次操作选择成了第二种操作执行，当时口袋里的数个数 $<2$，那他也会很急。

小 L 希望在自己不会急的前提下，让最终所有操作进行完之后，口袋中留下的数的平均值尽可能大，你需要求出这个最大的平均值，平均值即 口袋中数的和 除以 口袋中的数个数。

输入格式

本题有多组数据。

第一行输入一个正整数 $T$ ，表示数据组数。

对于每组数据：第一行输入一个正整数 $n$ 表示事件个数，第二行输入 $n$ 个数，每个数为 $-1$ 或 $0$ 或 $1$ ，若为 $-1$ 则需要从口袋里拿出两个数，加起来再放回去，若为 $1$ 则会往口袋中添加一个 $1$ ，若为 $0$ 则可以从两种操作中任选一个执行。

输出格式

对于每组数据：

若无法做到，输出一行一个 $-1$。

否则，一行两个正整数 $p,q$ ，$\frac{p}{q}$ 为答案的最简分数形式，即 $gcd(p,q)=1$。

样例

6
7
1 1 1 -1 1 1 -1
4
1 0 -1 0
4
0 -1 -1 0
1
0
2
0 0
1
-1

3 2
3 1
-1
1 1
2 1
-1

提示

数据范围

对于 $20\%$ 的数据，保证 $1\le n\le 10$。

对于另外 $30\%$ 的数据，保证 $1\le n\le 1000$。

对于 $100\%$ 的数据，保证 $1\le n\le 10^6,1\le T\le 5$。