B. The Good Judge
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

"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:

  • Choose an integer number $$$x$$$ and multiply all elements of $$$a$$$ by $$$x$$$.
  • Choose an integer number $$$x$$$ and multiply all elements of $$$b$$$ by $$$x$$$.

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.

Input

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$$$.

Output

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)$$$.

Example
Input
1
5
15 18 9 12 6
8 20 6 100 66
Output
2