题号：NC16779
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 128 M，其他语言256 M
64bit IO Format: %lld
题目描述
黑妹又来玩游戏了，这次她面对的是两个长度为n的正整数序列A和B，并且她要维护两个二元序对集合S1和S2，初始时这两个集合是空的，每一次她可以进行一次操作，
选择满足以下条件的两个序对(i, j)和(p, q)，
1.(i, j)不在S1中并且(p, q)不在S2中。
2. Ai < Bj, Aq > Bp。
3. Ai 和 Bj 不互质, Aq 和 Bp 不互质。
4. gcd(Ai, Bj) 和 gcd(Aq, Bp) 不互质。
然后把(i, j)加入集合S1，(p, q)加入集合S2。
但是她又很快玩腻了这个游戏，她现在想知道她最多能进行多少次操作。
输入描述:
第一行一个整数T表示测试数据组数。(1 ≤ T ≤ 10)
对于每组数据：
第一行一个整数n表示序列的长度。(1 ≤ n ≤ 400)
接下来一行n个整数表示序列A的每个元素。(1 ≤ Ai ≤ 109)
接下来一行n个整数表示序列B的每个元素。(1 ≤ Bi ≤ 109)
输出描述:
对于每组数据输出一行表示答案。
示例1
输入
复制
2
4
5 2 3 4
5 2 3 4
4
2 5 6 14
3 4 7 10