题目内容

给定两个长度为 $n$ 的整数序列 $A$ 和 $B$。每一步操作可以选择 $A$ 中若干个值相同的元素，并将它们的值同时乘以 $2$。

你的目标是通过若干次操作，使序列 $A$ 的元素多重集合与序列 $B$ 的元素多重集合完全一致（即每种值的出现次数相同，与顺序无关）。

请求出所需的最少操作次数；如果无法实现，则输出 $-1$。

元素个数 $n$ 不超过 $10^5$，所有数的取值范围为 $1$ 到 $10^9$。测试数据组数 $T$ 不超过 $10^5$，且所有测试数据的 $n$ 之和不超过 $5 imes 10^5$。

输入描述

第一行输入一个整数 $T$，表示测试数据组数。每组测试数据格式如下： 第一行输入一个整数 $n$，表示序列长度。 第二行输入 $n$ 个整数 $a_1, a_2, \dots, a_n$，表示序列 $A$。 第三行输入 $n$ 个整数 $b_1, b_2, \dots, b_n$，表示序列 $B$。

输出描述

对于每组测试数据，输出一行一个整数，表示最少操作次数；若无法实现，则输出 $-1$。

样例1

输入

2
2
2 6
4 6
2
6 5
12 3

输出

1
-1

说明

第一组数据： 将 $A=[2,6]$ 和 $B=[4,6]$ 中的每个数分解为“奇数部分”和 $2$ 的幂次。 $2 = 1 imes 2^1$，奇数部分为 1，幂次为 1；$6 = 3 imes 2^1$，奇数部分为 3，幂次为 1。 $4 = 1 imes 2^2$，奇数部分为 1，幂次为 2；$6 = 3 imes 2^1$，奇数部分为 3，幂次为 1。 奇数部分 3 在两序列中数量和幂次均一致，无需操作。 奇数部分 1 在 $A$ 中只有 $1$ 个（幂次 $1$），在 $B$ 中也有 $1$ 个（幂次 $2$）。由于只能将元素翻倍，我们需要将 $A$ 中值为 $2$ 的元素乘以 $2$ 变成 $4$，这恰好需要 $1$ 次操作。 第二组数据： $A=[6,5]$，奇数部分分别为 3 和 5；$B=[12,3]$，奇数部分分别为 3 和 1。出现了 $A$ 中有 5 而 $B$ 中没有的奇数部分，因此不可能使两个多重集合一致，输出 $-1$。

样例2

输入

1
3
1 1 2
4 2 1

输出

2

说明

分解所有数字（奇数部分，幂次）： $A$ 中：$1 = 1 imes 2^0$（两个），$2 = 1 imes 2^1$（一个）； $B$ 中：$4 = 1 imes 2^2$，$2 = 1 imes 2^1$，$1 = 1 imes 2^0$。 奇数部分只有 1，共 $3$ 个元素。统计各幂次的出现次数： $A$：幂次 $0$ 有 2 个，幂次 $1$ 有 1 个； $B$：幂次 $0$ 有 1 个，幂次 $1$ 有 1 个，幂次 $2$ 有 1 个。 从低幂次向高幂次调整： 幂次 $0$：$A$ 比 $B$ 多出 $1$ 个，需将这 $1$ 个 $1$ 同时乘以 $2$，花费 $1$ 次操作，此时它们变为幂次 $1$ 的 $2$。 幂次 $1$：$A$ 原有 $1$ 个 $2$，加上从低幂次升上来的 $1$ 个，共 $2$ 个；$B$ 需要 $1$ 个，多出 $1$ 个。我们可仅选其中 $1$ 个 $2$ 乘以 $2$，花费 $1$ 次操作变为 $4$（幂次 $2$）。最终三个数变为 $1,2,4$，与 $B$ 一致。总共 $2$ 次操作。

样例3

输入

1
1
3
6

输出

1

说明

只有单个元素：$A=[3]$，$B=[6]$。 分解：$3 = 3 imes 2^0$，奇数部分 3，幂次 0；$6 = 3 imes 2^1$，奇数部分 3，幂次 1。 奇数部分一致且数量相同。幂次从 $0$ 到 $1$ 多出 $1$ 个，需将 $3$ 乘以 $2$ 一次变为 $6$，最小操作次数为 1。