题目背景

有一天，当 $\mathrm{Sunny}$ 闲逛的时候，发现了一个按钮。

好奇心驱使他按下了这个按钮。

突然间，天旋地转 $\dots$

题目描述

醒来之后，$\mathrm{Sunny}$ 发现自己站在一个奇怪的地方。

这个地方有 $n$ 个平台，形成了一个环。

这时，$\mathrm{Ethan}$ 的声音响起：

“哈哈哈哈哈哈，恭喜你，你是第一个来到死亡之地的人。”

“正如你所看到的，这个地方有 $n$ 个平台，你现在站在 $0$ 号平台上。”

“剩余平台按顺时针编号 $1,2,3\dots n-1$，也就是说，你身后的那个平台就是 $n-1$ 号平台。”

“你每次能够顺时针跳 $i$ 个平台，$i\in[1,n]$，每次的 $i$ 可以不一样。”

“如果你能够经过所有平台（初始 $0$ 号位置不算），那你就能逃出死亡之地了。”

（这里指的是一开始的 $0$ 号位置不算经过，需要再次经过 $0$ 号位置）

“不过，这样太简单了，我会给你一些数 $a_j$，表示你不能一次顺时针跳 $a_j$ 个平台。”

“还有，你必须要用最少的跳跃次数完成我的任务。”

“如果你不能满足我的上面两个要求，所有平台就会消失，你将会掉入下面的岩浆之中。”

现在，$\mathrm{Sunny}$ 想知道他是否可能逃出这个地方。

如果不行，输出-1，否则输出他最少所需的跳跃次数。

因为 $\mathrm{Sunny}$ 觉得死亡之地实在是太有趣了，所以他决定多玩几次，多组数据。

输入格式

第一行，一个正整数 $T$，代表数据组数。

接下来 $2\times T$ 行，共 $T$ 组数据：

第 $2\times i-1$ 行，两个整数 $n,k$，$k$ 代表该组数据 $a_j$ 的个数。

第 $2\times i$ 行，$k$ 个数，第 $j$ 个数表示 $a_j$。

输出格式

$T$ 行，第 $i$ 行表示第 $i$ 组数据的输出。

3
5 4
1 2 3 4
5 4
1 2 4 5
6 3
1 3 5

-1
5
-1

提示

---

样例说明

第一组数据：

$\mathrm{Sunny}$ 每次只能顺时针跳 $5$ 个平台，易知不可能完成。

第二组数据：

$\mathrm{Sunny}$ 每次只能顺时针跳 $3$ 个平台，跳 $5$ 次即可。

---

数据范围与约定

$0\leq k\leq n\leq 10^6,1\leq n$。

保证 $\sum{n_i}\leq 3*10^6,a_j\leq n$，且互不相同。

测试点 $1:5\%,n=1$。

测试点 $2:5\%,n\leq5$。

测试点 $3:10\%,n\leq15$。

测试点 $4:15\%,n\leq300$。

测试点 $5:25\%,n\leq5000$。

测试点 $6:40\%,n\leq10^6$。

---

梦醒了……