问题描述

给定一个长度为 $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$ 行，每行一个数，表示对应的数据的答案。

输入样例

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

输出样例

2
11
1975
-1

样例1解释

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

数据范围

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