题目描述

戴夫准备在后院种植植物来抵御僵尸的进攻。

他有 $n$ 种植物可以选择，每种植物有两个属性：攻击力 $s$ 和类型 $t$。其中 $t=1$ 表示这是一种特殊植物（如坚果墙），$t=0$ 表示普通攻击植物。

为了形成有效的防御体系，戴夫需要选择最大数量的植物，使得对于每个选中的植物 $i$，要么它是特殊植物（$t=1$），要么存在一个选中的植物 $j$ （注意可以是自己），植物 $i$ 的攻击力能整除那个植物 $j$ 的攻击力加1（即 $s_i|(s_j+1)$，表示植物间有配合效果）。

输入格式

第一行一个整数 $T$ 表示多组数据。

对于每组数据：

第一行一个整数 $n$。

接下来一行 $n$ 个数，第 $i$ 个表示 $s_i$。

接下来一行 $n$ 个数，第 $i$ 个表示 $t_i$。

输出格式

对于每组数据：

输出一行一个整数，表示最多能选择的植物数量。

样例 1

1
6
2 3 4 5 6 7
0 0 0 0 0 0

6

样例解释 1

所有元素都保留。

样例 2

1
4
2 7 9 111
0 0 0 1

3

样例解释 2

选择攻击力为 $\{2,7,111\}$ 的三种植物。攻击力为111的是特殊植物，攻击力为2的植物能整除攻击力为7的植物+1（即$2|8$），攻击力为7的植物能整除攻击力为111的植物+1（即$7|112$）。

样例 3

见下发文件 $\text{ex_number3.in/out}$。

数据范围及约定

对于所有测试点满足 $T\leq 10^4,\Sigma n\leq 10^6,1\leq s_i\leq 3\times 10^6,t_i \in\{0,1\}$。

每个测试点的具体限制见下表：

\begin{array}{|c|c|c|} \hline \textbf{测试点编号} & \Sigma n & \textbf{特殊性质} \\ \hline 1\sim 4 & \leq 20 & \textbf{无} \\ \hline 5\sim 8 & \leq 5000 & s_i\leq 5000 \\ \hline 9\sim 12 & \textbf{无} & s_i\leq 5000 \\ \hline 13\sim 20 & \textbf{无} & \textbf{无} \\ \hline \end{array}