djb 的联通块

题目描述

现在 djb 有好多巨大的图，图上有 $n$ 个点，编号分别为 $1 \sim n$

而图里的边非常非常多，为了简化题目，djb 写了一个数字集合 $S$

如果两个点 $x,y$ 满足 $|x - y| \in S$,则 $x,y$之间存在一条无向边

现在 djb 想知道这个图里有多少个联通块？

输入格式

输入第一行包含一个非负整数 $T$，表示有 $T$ 组询问

对于每组询问，第一行两个正整数 $n,m$ 表示图上有 $n$ 个点，集合 $S$ 中有 $m$ 个数字

第二行包含 $m$ 个不同的整数 $S_i$，表示每个集合中的每个数字

输出格式

对于每组询问输出联通块个数

数据规模

对于 $100$ 的数据满足 $\sum m \leq 2 * 10^5, 2 \leq n \leq 10^{18}, 1 \leq S_i < n$

对于第 $1 \sim 2$ 组数据满足 $n \leq 10^5, \sum m \leq 50, m \leq 10$

对于第 $3 \sim 4$ 组数据满足 $m \geq 1000, S$ 为随机生成

对于第 $5 \sim 9$ 组数据满足 $\sum n \leq 10^5$

对于第 $10 \sim 11$ 组数据满足 $m \leq 2$

对于第 $12 \sim 14$ 组数据满足 $m \leq 15$

对于第 $15 \sim 16$ 组数据满足 $m \leq 30$

对于第 $17 \sim 20$ 组数据没有特殊限制

样例输入

3
6 2
2 3
5 1
2
658 3
219 451 581

样例输出

1
2
12