← 返回题目列表

Codeforces · 1728/C

C. 数字对数

中文机器翻译题面 查看原题

让我们将正整数 $$$x$$$ 定义为 $$$x$$$ 以 10 为基数表示的长度(不带前导零)。我喜欢称其为数字对数。如果您熟悉的话,类似于数字根。

给定两个数组 $$$a$$$ 和 $$$b$$$,每个数组包含 $$$n$$$ 正整数。在一项操作中,您执行以下操作:

1. 从$$$1$$$到$$$n$$$中选择一些整数$$$i$$$;
2. 将 $$$f(a_i)$$$ 分配给 $$$a_i$$$ 或将 $$$f(b_i)$$$ 分配给 $$$b_i$$$。

如果您可以重新排列两个数组中的元素,使它们相等(例如,对于从 $$$1$$$ 到 $$$n$$$ 的所有 $$$i$$$,$$$a_i = b_i$$$,则认为两个数组彼此相似。

使 $$$a$$$ 和 $$$b$$$ 彼此相似所需的最少操作次数是多少?

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 每个数组中的元素数量。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i < 10^9$$$)。

第三行包含 $$$n$$$ 整数 $$$b_1, b_2, \dots, b_n$$$ ($$$1 \le b_j < 10^9$$$)。

所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,打印使 $$$a$$$ 和 $$$b$$$ 彼此相似所需的最少操作数。

示例

输入 #1

4
1
1
1000
4
1 2 3 4
3 1 4 2
3
2 9 3
1 100 9
10
75019 709259 5 611271314 9024533 81871864 9 3 6 4865
9503 2 371245467 6 7 37376159 8 364036498 52295554 169

输出 #1

2
0
2
18

注意

在第一个测试用例中,您可以将数字对数应用于 $$$b_1$$$ 两次。

在第二个测试用例中,数组已经彼此相似。

在第三个测试用例中,您可以首先将数字对数应用于$$$a_1$$$,然后应用于$$$b_2$$$。