调色题Ⅱ
题号：NC313718
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

\hspace{15pt}本题与《调色题Ⅰ》共享部分题目背景，但是所求内容与范围均不同，我们建议您重新阅读题面。

\hspace{15pt}www.com 有 n 个待调色的方格，第 i 个方格的初始颜色编号为 a_i。此外，他还有 m 种颜料，第 i 种颜料的编号为 b_i。
\hspace{15pt}www.com 每次可以选择一个方格 i 和一种颜料 j，进行一次调色操作。记该方格当前颜色编号为 a_i'，则操作后更新为 \gcd(a_i', b_j)。

\hspace{15pt}每种颜料可重复使用，次数不限；同一方格可被多次调色。他想要让所有方格的颜色编号完全相同。请你求出实现该目标所需要的最少操作次数，若无法让所有方格的颜色编号完全相同，则输出 -1。

【名词解释】
\hspace{15pt}\gcd：最大公约数，指两个或多个整数共有约数中最大的一个。例如，12 和 30 的公约数有 1,2,3,6，其中最大的约数是 6，因此记作 \gcd(12,30)=6。

输入描述:

\hspace{15pt}每个测试文件均包含多组测试数据。第一行输入一个整数 T\left(1\leq T\leq 20\right) 代表数据组数，每组测试数据描述如下：

\hspace{15pt}第一行输入两个整数 n 和 m \left(1 \le n, m \le 500\right)，分别表示方格数量和颜料种类。
\hspace{15pt}第二行输入 n 个整数 a_1, a_2, \dots, a_n \left(1 \le a_i \le 5\times 10^5\right)，表示各方格的初始颜色。
\hspace{15pt}第三行输入 m 个整数 b_1, b_2, \dots, b_m \left(1 \le b_i \le 5\times 10^5\right)，表示各颜料的编号。

\hspace{15pt}除此之外，保证单个测试文件的 n 之和、m 之和均不超过 500。

输出描述:

\hspace{15pt}对于每一组测试数据，新起一行。若无法让所有方格的颜色编号完全相同，输出 -1；否则，输出一个整数，表示最少的操作次数。
示例1

输入

复制 
3
2 1
2 4
4
5 3
60 90 150 180 210
240 60 90
5 4
9 3 7 10 11
5 8 9 2

输出

复制 
-1
6
5

说明

\hspace{15pt}对于第一组测试数据，可以证明无法让所有方格的颜色编号完全相同。

\hspace{15pt}对于第二组测试数据，一种操作次数最小的方案为：
\hspace{23pt}\bullet\,选择方格 1 和颜料 3，方格颜色变为 \{{{\color{orange}{30}}},90,150,180,210\}；
\hspace{23pt}\bullet\,选择方格 2 和颜料 2，方格颜色变为 \{30,{{\color{orange}{30}}},150,180,210\}；
\hspace{23pt}\bullet\,选择方格 3 和颜料 2，方格颜色变为 \{30,30,{{\color{orange}{30}}},180,210\}；
\hspace{23pt}\bullet\,选择方格 4 和颜料 1，方格颜色变为 \{30,30,30,{{\color{orange}{60}}},210\}；
\hspace{23pt}\bullet\,选择方格 4 和颜料 3，方格颜色变为 \{30,30,30,{{\color{orange}{30}}},210\}；
\hspace{23pt}\bullet\,选择方格 5 和颜料 3，方格颜色变为 \{30,30,30,30,{{\color{orange}{30}}}\}。