G. Inscryption
time limit per test
3 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

You are lost deep in the forest. The only thing that is still accompanying you is your stoat. It has an initial attack of $$$1$$$. It is your only Beast at the beginning.

A single path revealed itself before you. On the path are $$$n$$$ event marks. Every event mark falls into one of the following:

  • Card Choice: A dentizen of the forest shall grace your caravan. You will gain an additional Beast. It will always have an initial attack of $$$1$$$.
  • Mysterious Stone: You will be compelled to make a worthy sacrifice. Two Beasts from your caravan of your choice will perform the ritual: one to be lost forever, adding its attack onto the other. Failure to perform the ritual will forbid you to go on.
  • Fork in the Road: You will choose to trigger either a Card Choice or a Mysterious Stone. You can't choose to do nothing.

When you walk through the winding road, the event marks will be triggered in order. Find out the maximum average of attack for your Beasts you can achieve after all event marks are completed.

Input

There are multiple test cases. The first line of the input contains an integer $$$T$$$ indicating the number of test cases. For each test case:

The first line contains one integer $$$n$$$ ($$$1 \le n \le 10^6$$$) indicating the number of event marks.

The second line contains $$$n$$$ integers $$$a_1, a_2, \cdots, a_n$$$ ($$$-1 \le a_i \le 1$$$) where $$$a_i$$$ indicates the type of the $$$i$$$-th event mark: $$$1$$$ means a Card Choice, $$$-1$$$ means a Mysterious Stone and $$$0$$$ means a Fork in the Road.

It's guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^6$$$.

Output

For each test case output one line.

If it is impossible to complete all event marks, output one integer $$$-1$$$.

Otherwise it can be proven that the answer is a rational number $$$\frac{p'}{q'}$$$. Output two integers $$$p$$$ and $$$q$$$ where $$$\frac{p}{q}$$$ is the simplest fraction representation of $$$\frac{p'}{q'}$$$.

$$$\frac{p}{q}$$$ is the simplest fraction representation of $$$\frac{p'}{q'}$$$ if $$$\frac{p}{q} = \frac{p'}{q'}$$$ and the greatest common divisor of $$$p$$$ and $$$q$$$ is $$$1$$$.

Example
Input
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
Output
3 2
3 1
-1
1 1
2 1
-1
Note

The first sample test case is explained as follows:

EventActionBeasts
$$$1$$$Gain additional Beast$$$\{1, 1\}$$$
$$$1$$$Gain additional Beast$$$\{1, 1, 1\}$$$
$$$1$$$Gain additional Beast$$$\{1, 1, 1, 1\}$$$
$$$-1$$$Choose Beasts with attack $$$1$$$ and $$$1$$$$$$\{2, 1, 1\}$$$
$$$1$$$Gain additional Beast$$$\{2, 1, 1, 1\}$$$
$$$1$$$Gain additional Beast$$$\{2, 1, 1, 1, 1\}$$$
$$$-1$$$Choose Beasts with attack $$$2$$$ and $$$1$$$$$$\{3, 1, 1, 1\}$$$

The average attack is $$$\frac{3 + 1 + 1 + 1}{4} = \frac{6}{4} = \frac{3}{2}$$$.

The second sample test case is explained as follows:

EventActionBeasts
$$$1$$$Gain additional Beast$$$\{1, 1\}$$$
$$$0$$$Trigger Card Choice and gain additional Beast$$$\{1, 1, 1\}$$$
$$$-1$$$Choose Beasts with attack $$$1$$$ and $$$1$$$$$$\{2, 1\}$$$
$$$0$$$Trigger Mysterious Stone and choose Beasts with attack $$$2$$$ and $$$1$$$$$$\{3\}$$$

The average attack is $$$\frac{3}{1}$$$.

The third sample test case is explained as follows:

EventActionBeasts
$$$0$$$Trigger Card Choice and gain additional Beast$$$\{1, 1\}$$$
$$$-1$$$Choose Beasts with attack $$$1$$$ and $$$1$$$$$$\{2\}$$$
$$$-1$$$Not enough BeastsFailure