小 z 很无聊。
小 z 要玩游戏。
小 z 有 $N$ 个新游戏，第 $i$ 个游戏看上去的有趣程度为 $w_i$。
小 z 很挑，他只会玩看上去的有趣程度是自己兴奋程度整数倍的游戏。
由于游戏实际上有好玩的也有不好玩的，玩完第 $i$ 个游戏后，小 z 的兴奋程度会变为 $e_i$。
已知小 z 初始兴奋程度为 $1$，请问小 z 有多少个游戏可能会玩两次？
输入格式
第一行一个正整数 $T$，表示测试数据组数，最多 $10$ 组。
对于每组测试数据：
- 第一行一个正整数 $N$，表示游戏的个数。
- 第二行 $N$ 个正整数，第 $i$ 个数 $w_i$，表示第 $i$ 个游戏看上去的有趣程度为 $w_i$。
- 第三行 $N$ 个正整数，第 $i$ 个数 $e_i$，表示小 z 玩完第 $i$ 个游戏后，小 z 的兴奋程度会变为 $e_i$。
输出格式
共 $T$ 行。
每行一个正整数，表示对应测试数据，小 z 可能会玩两次的游戏数量。
样例数据
样例输入
5 1 100000 100000 5 1 2 6 15 35 5 7 9 2 3 5 2 3 5 35 21 7 11 7 3 2 10 6 15 77 12 24 37 35 99 55 42 4 2 5 7 11 3 6 8 9 10 10 6540 5604 567 57065 60 670 6870 1230 465 6540 12 5 37 3 34 13 17 18 10 12
样例输出
1 3 3 8 5
子任务
| 数据编号 | $T$ | $N$ | $w_i, e_i$ | 其他约束 |
|---|---|---|---|---|
| $1$ | $= 10$ | $\leq 100$ | $\leq 10^5$ | 无 |
| $2$ | ||||
| $3$ | ||||
| $4$ | $\leq 3\,000$ | 一组数据中 $e_i$ 两两不同 $w_i$ 两两不同 |
||
| $5$ | $\leq 30\,000$ | |||
| $6$ | $\leq 10^5$ | |||
| $7$ | $\leq 30\,000$ | $e_i$ 为 $1$ 或 质数 | ||
| $8$ | $\leq 10^5$ | |||
| $9$ | $\leq 30\,000$ | 无 | ||
| $10$ | $\leq 10^5$ | |||