1357: 数论三角洲（easy version）

三角洲中，威龙一直是打法最欧美的武将类干员之一，其中一个关键是因为威龙拥有一个喷气背包，一次喷气可以让威龙几乎闪现到目标地点。携带这样一个强力的位移技能，必然要搭配 S12K 这种近战威力巨大的霰弹枪。组合技为：先喷气闪现到敌人脸上，再用 S12K 瞬秒敌人。

现在，有一狭窄的长度为 $n$ 的环形区域，顺时针上，环形区域分为 $n$ 个小格子，格子编号分别为 $0,1,2,\dots ,n-1$ 每个格子上有一个邪恶 GTI 阵营的 xjj 指挥官麾下的士兵，最开始，威龙将会被空降至 $0$ 号格子，他拥有 $m$ 种喷气模式，喷气长度分别为 $d_1,d_2,\dots ,d_m$ ，第 $i$ 种喷气可以让他从 $x$ 位置喷气到 $(x + d_i) % n$ 的位置上，如果威龙所在的格子上还有活着的xjj的士兵，那么威龙会立刻消灭他。

为保持机动性，威龙不走路，只用喷气，每次可以任选一种喷气，总喷气次数和每种喷气使用次数不限，威龙只能在每次喷气到达目的地后开枪，威龙希望尽可能消灭这 $n$ 个士兵。

由于环形区域挺大的，喷气背包的种类也很多，威龙先生的脑子要过载了，于是威龙从正义的哈夫克阵营指挥官 Libra_Minister 手中申请了脑机接口，但笨蛋威龙是个武将，但他想知道怎么写判断最多能杀几个 GTI 士兵的算法，还请你来帮助他！

第一行输入一个正整数 $t$ ，代表 $t$ 次询问。 ​ 每个询问的第一行输入一个整数 $n(1\leq n \leq 2\times 10^5)$ ，和一个整数 $m(1\leq m \leq 2\times 10^5)$ ，表示环形区域的长度和喷气背包数量。 ​ 每个询问的第二行输入 $m$ 个整数 $d_i (1 \le d_i \le 10^9)$ 。 ​ 输入保证 $\sum n\le 4 \times 10^5$ ， $\sum m\le 4 \times 10^5$ 。

​ 对于每个询问一行输出一个整数 $num(0 \le num \le n)$ 代表他一共能杀最多多少个士兵。

2
4 2
2 4
6 4
1 2 3 8

2
6