Để kích thích tư duy của Gon, cô giáo quyết định cho cậu một bài toán.

Cho một dãy số a gồm \(n\) phần tử \(a_1, a_2,..., a_n\). Gon có thể chọn 1 số trong dãy và thêm hoặc bớt số đó \(1\) đơn vị. Hành động này có thể lặp đi lặp lại nhiều lần.

Bây giờ, cô muốn Gon sử dụng thao tác trên để cho ra một dãy có tích bằng 1, hay \(a_1 * a_2 * ... * a_n = 1\).

Ví dụ, với \(n = 3\) và \(a = [-1, -3, 0]\), ta có thể thực hiện 2 lần thêm 1 vào -3 và thực hiện 1 lần thêm 1 vào 0 để được dãy \([-1, -1, 1] = (-1) * (-1) * 1 = 1\).

Gon dễ dàng giải quyết vấn đề nhưng cậu tự hỏi liệu không biết cách mình làm có sử dụng ít thao tác nhất không?

Bạn hãy giúp Gon tìm số lần thực hiện thao tác ít nhất mà giải quyết được vấn đề của cô giáo nhé.

Input

• Dòng đầu tiên là số test case \(t\) \((1 \le \)t\( \le 10)\)
• Tiếp theo là \(n\) độ dài dãy \((1 \le \)n \le 10^5)\(, và các phần tử trong dãy (-10^9 \le \)ai~ \le 10^9).

Output

• In ra một số duy nhất là kết quả của bài toán.

Example

Input 1:

1
2
-1 1

Output 1:

2

Input 2:

2
4
0 0 0 0
5
-5 -3 5 3 0

Output 2:

4
13