[Solution] Digital Logarithm Codeforces Solution

C. Digital Logarithm

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Let's define 𝑓(𝑥)$f(x)$ for a positive integer 𝑥$x$ as the length of the base-10 representation of 𝑥$x$ without leading zeros. I like to call it a digital logarithm. Similar to a digital root, if you are familiar with that.

You are given two arrays 𝑎$a$ and 𝑏$b$, each containing 𝑛$n$ positive integers. In one operation, you do the following:

1. pick some integer 𝑖$i$ from 1$1$ to 𝑛$n$;
2. assign either 𝑓(𝑎𝑖)$f(a_i)$ to 𝑎𝑖$a_i$ or 𝑓(𝑏𝑖)$f(b_i)$ to 𝑏𝑖$b_i$.

Two arrays are considered similar to each other if you can rearrange the elements in both of them, so that they are equal (e. g. 𝑎𝑖=𝑏𝑖$a_i=b_i$ for all 𝑖$i$ from 1$1$ to 𝑛$n$).

What's the smallest number of operations required to make 𝑎$a$ and 𝑏$b$ similar to each other?

Input

The first line contains a single integer 𝑡$t$ (1≤𝑡≤104$1\le t\le {10}^4$) — the number of testcases.

The first line of the testcase contains a single integer 𝑛$n$ (1≤𝑛≤2⋅105$1\le n\le 2\cdot {10}^5$) — the number of elements in each of the arrays.

Solution Click Below:-  👉CLICK HERE👈

👇👇👇👇👇

The second line contains 𝑛$n$ integers 𝑎1,𝑎2,…,𝑎𝑛$a_1,a_2,\dots ,a_n$ (1≤𝑎𝑖<109$1\le a_i<{10}^9$).

The third line contains 𝑛$n$ integers 𝑏1,𝑏2,…,𝑏𝑛$b_1,b_2,\dots ,b_n$ (1≤𝑏𝑗<109$1\le b_j<{10}^9$).

The sum of 𝑛$n$ over all testcases doesn't exceed 2⋅105$2\cdot {10}^5$.

Output

For each testcase, print the smallest number of operations required to make 𝑎$a$ and 𝑏$b$ similar to each other.

Note

In the first testcase, you can apply the digital logarithm to 𝑏1$b_1$ twice.

In the second testcase, the arrays are already similar to each other.

In the third testcase, you can first apply the digital logarithm to 𝑎1$a_1$, then to 𝑏2$b_2$.