题目描述

给定一个长度为 $n$ 的整数序列 $a$（下标从 $1$ 开始），你可以进行以下操作若干次：

• 选择一个区间 $[l,r]$，对于所有 $i \in N,x \in \{0,1\},l+3i+x \le r$，将 $a_{l+3i+x}$ 增加 $(−1)^x$。
  问至少需要多少次操作，才能使 $a$ 序列的所有位置值均为0，若无解，则输出 $−1$。

输入格式

第一行两个正整数 $T,n$，表示数据组数以及每组数据的序列长度。
接下来 $T$ 行，每行一个长度为 $n$ 的整数序列 $a$。

输出格式

T 行，每行一个数，表示对应的数据的答案。

样例输入 #1

4 5
-1 0 1 -1 1
-1 -2 -3 -4 5
-11 -45 14 -1919 810
-1 -2 3 4 -5

样例输出 #1

2
11
1975
-1

样例解释 #1

对于第一组数据，进行操作 $[1,5],[2,3]$ 即可。

样例 2,3,4,5

见附加文件。

数据范围

对于所有测试数据，保证 $T =30$。

提示

题目顺序是瞎排的。