「SWTR-1」Escape

题目背景

有一天,当 $\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$ 组数据的输出。

输入输出样例

输入样例 #1

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

输出样例 #1

-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$。 --- 梦醒了……