Ali loves ice coffee, so Ahmad offers him ice coffee if he can solve this problem. Ali is not good at problem solving, so he asked for your help to solve the problem and get the Ice Coffee.
Given two arrays A and B the goal is to make array A equal to B.
There are two types of operations :
$$$next(x)$$$ = the greatest divisor of the number $$$x$$$, excluding $$$x$$$ itself.
For example, $$$next(12) = 6$$$, $$$next(18) = 9$$$.
Given two arrays print the minimum number of operations (possibly zero) to make arrays $$$A$$$ and $$$B$$$ equal.
Two arrays $$$A$$$ and $$$B$$$ of length $$$n$$$ are considered equal if $$$A_{i} = B_{i}$$$ for all $$$i$$$ $$$(1 \le i \le n)$$$
The first line contains a single integer $$$t$$$ $$$(1 \le t \le 10^4)$$$ - The number of test cases.
Each test case has 3 lines :
The first line contains a single integer $$$n$$$ $$$(1 \le n \le 10^5)$$$ - The length of the two arrays.
The second line contains $$$n$$$ integers $$$A_{1}, A_{2}...,A_{n}$$$ $$$(1 \le A_{i} \le 10^7)$$$ - elements of the array $$$A$$$.
The third line contains $$$n$$$ integers $$$B_{1}, B_{2}...,B_{n}$$$ $$$(1 \le B_{i} \le 10^7)$$$ - elements of the array $$$B$$$.
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2.10^5$$$.
For each test case, print one integer - The minimum number of operations (possibly zero) to make arrays $$$A$$$ and $$$B$$$ equal.
3 4 4 5 12 1 8 3 9 2 2 5 4 10 6 1 2 8
7 5 2
