时间限制：1秒　　内存限制：256M

---

【题目描述】

　　求在小于等于 \(n\) 的正整数中有多少个 \(X\) 满足：
　　　\(X = b[1]\ (mod\ a[1])\)
　　　\(X = b[2]\ (mod\ a[2])\)
　　　………
　　　\(X = b[m]\ (mod\ a[m])\)

【输入格式】

　　输入数据的第一行为一个正整数 \(T\)，表示有 \(T\) 组测试数据。每组测试数据的第一行为两个正整数 \(n，m\) ，表示 \(X\) 小于等于 \(n\)，数组 \(a\) 和 \(b\) 中各有 \(m\) 个元素。接下来两行，每行各有 \(m\) 个正整数，分别为 \(a\) 和 \(b\) 中的元素。

【输出格式】

　　对应每一组输入，在独立一行中输出一个正整数，表示满足条件的 \(X\) 的个数。

【输入输出样例】

　Input

3
10 3
1 2 3
0 1 2
100 7
3 4 5 6 7 8 9
1 2 3 4 5 6 7
10000 10
1 2 3 4 5 6 7 8 9 10
0 1 2 3 4 5 6 7 8 9

　Output

1
0
3

【数据限制】

　　对于 \(100\%\) 的数据，\(1≤n≤10^9\)，\(1≤m≤10\)，\(1≤a[i]≤10\)。

【来源】

　　Mr.he