数组同构

题号：NC300462
时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

$\hspace{15pt}$ 定义变换函数：
$\hspace{23pt}\bullet\,$ 将一个正整数 $x$ 用其二进制表示中 $1$ 的个数替换，记作 $g(x)$ （即 $\operatorname{popcount}$ ）；
$\hspace{15pt}$ 给定两个长度均为 $n$ 的正整数数组 $A$ 和 $B$ ；
$\hspace{15pt}$ 你可以对 $A$ 或 $B$ 中的任意元素反复执行以下操作，每次操作计数 $1$ ：
$\hspace{23pt}\bullet\,$ 将该元素 $x$ 替换为 $g(x)$ ；

$\hspace{15pt}$ 当且仅当存在置换 $\pi$ ，使得对所有 $1\leqq i\leqq n$ 都有 $A_i = B_{\pi(i)}$ ，也就是两个数组都排序后完全相同，我们称 $A$ 与 $B$ 同构。请计算使 $A$ 与 $B$ 同构所需的最少操作次数。

$\hspace{15pt}$ 可以证明题目一定有解。

输入描述:

第一行输入一个整数 ，表示测试用例数； 
每个测试用例输入格式如下： 
第一行输入一个整数 ； 
第二行输入  个整数 ； 
第三行输入  个整数 ； 
保证所有测试用例中 。

输出描述:

对于每个测试用例，输出一行整数——使  与  同构的最少操作次数。

示例1

输入

复制

输出

复制

2
1

说明

初始时，； 
对  中元素  执行一次变换，得到 ，此时 ； 
对  中一个元素  执行一次变换，得到 ，此时 ； 
此时两数组的元素可以一一匹配，故最少操作数为 。 

在第二个测试用例中：仅需将  中的  变换为 ，得到 ，与  相同，操作数为 。