（trans）

给定一个长度为 $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]$ 即可。

数据范围

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

| 测试点编号 | $n=$ | $|a_i|\le$ | | :--------: | :------------: | :------------: | | $1$ | $5$ | $5$ | | $2$ | $20$ | $10$ | | $3$ | $70$ | $100$ | | $4,5$ | $200$ | $10^{10}$ | | $6,7$ | $2\times 10^3$ | $2\times 10^3$ | | $8,9,10$ | $3\times 10^4$ | $10^{10}$ |