"I added a problem, I deserve to be a judge", Radi said.
"You keep adding problems and work on them and over time, you will be a judge", the chief judge responded.
"No, I'm a judge", Radi insisted.
However, Radi added one problem and did no work on it, so he wasn't a judge.
The problem states that you are given two arrays $$$a$$$ and $$$b$$$ of $$$n$$$ integer numbers. You can do each of the following operations any number of times in any order:
You need to find the minimum number of operations needed so that $$$GCD(a_1, a_2 \dots a_n) = GCD(b_1, b_2 \dots b_n)$$$.
The greatest common divisor (GCD) of two or more integers is the largest positive integer that divides each of the integers.
The first line of the input contains a single integer number $$$t$$$ $$$(1 \le t \le 10^4)$$$. The number of test cases.
The first line of each test contains a single integer number $$$n$$$ $$$(1 \le n \le 2 \times 10^5)$$$. The number of elements in both arrays $$$a$$$ and $$$b$$$.
The second line of each test case contains $$$n$$$ space-separated integer numbers $$$a_1, a_2 \dots a_n$$$ $$$(1 \le a_i \le 10^6)$$$.
The third line of each test case contains $$$n$$$ space-separated integer numbers $$$b_1, b_2 \dots b_n$$$ $$$(1 \le b_i \le 10^6)$$$.
It is guaranteed that the sum of $$$n$$$ over all of the test cases does not exceed $$$2 \times 10^5$$$.
For each test case print a single line containing a single integer number. The minimum number of operations needed so that $$$GCD(a_1, a_2 \dots a_n) = GCD(b_1, b_2 \dots b_n)$$$.
1515 18 9 12 68 20 6 100 66
2