暂无测试数据。

信竞选手–蒜头君在计蒜客中组织一场模拟赛，他共准备了 $m$ 种奖品，每种奖品的数量无限多。

有 $n$ 名选手（编号为 $1\sim n$）参加了模拟赛，并获得蒜头君准备的奖品，第 $i$ 名选手获得的奖品数量为 $c_i$。

现在蒜头君需要为本次模拟赛拍照留念，他让 $n$ 名按照编号顺时针围成一个环。拍照的时候，蒜头君发现有些蒜头手中的奖品太多了，遮挡到了自己或者其他人。冥思苦想后，他想要找到一种方案，满足：

1. 每名选手不会被分到两个或两个以上的同类型奖品；
2. 相邻的两名选手不会被分到同类型的奖品。

请问是否能够找到：在不改变每名选手奖品数量的情况下，满足上述规则的方案。

输入格式

第一行输入一个正整数 $T$，表示数据的组数。

对于每组数据：

• 第一行输入两个以空格隔开的正整数 $n, m$，分别表示本组数据中选手的数量和奖品的种类数。
• 第二行输入 $n$ 个以空格隔开的整数 $c_i$，表示本组数据中第 $i$ 名选手获得的奖品数量。

输出格式

输出共 $T$ 行，每行一个整数。

第 $i$ 行表示第 $i$ 组数据的答案：

• 如果不能找到满足条件的方案，则输出 -1；
• 如果可以找到满足条件的方案，则输出 1。

数据范围

对于 $30\%$ 的数据，$1\leq n, m \leq 20$；

对于 $100\%$ 的数据，$1\leq T \leq 100,1\leq n \leq 2\times 10^5, 1\leq m \leq 10^8, 0\leq c_i \leq 10^5, \sum n \leq 10^7$。

2
3 3
2 1 1
4 4
2 2 2 2

-1
1