Equalize#12887

Equalize

1 second
256 megabytes
Hard

Let's call array [b_1, b_2, \ldots, b_m] good, if b_1\cdot b_2 \cdot \ldots \cdot b_m = b_1 + b_2 + \ldots + b_m.

You are given an array a_1, a_2, \ldots, a_n. In one operation, you can add any integer element to this array. What's the smallest number of operations you have to make to make it good?

Input

The first line contains a single integer (1 \le t \le 5\cdot 10^4)  — the number of test cases. The description of test cases follows.

The first line of each test case contains a single integer (1 \le n \le 2\cdot 10^5)  — the length of the array.

The second line of each test case contains integers a_1, a_2, \ldots, a_n (-10^6 \le a_i \le 10^6)  — the elements of the array.

It is guaranteed that the sum of over all test cases does not exceed 2\cdot 10^5.

Output

For each test case, output a single integer  — the smallest number of operations you have to make to make the array good.

Examples

Example 1

Loading
Loading

Note

In the first test case, the array is already good, as both product and sum are .

In the second test case, initially, the product is , and the sum is . We can add to this array, it will become [3, 2, 1], with both product and sum equal to .

In the third test case, we can add and to our array, it will become [1, 1, -1, 2, 1, 1, -2, 1], with both sum and product equal to .

In the fourth test case, the array [-1, 0, 1] is already good, with both product and sum equal to .

In the fifth test case, you can append to our array, it will become [1, -1, 2, -1, 1, 1, 3], with both sum and product equal to .