D. GCD of Pairs
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

It was the last hour before the regional contest scoreboard froze. The team from Aurora University had one problem left to test: their coach tossed two arrays onto the screen and challenged them with a playful quiz.

"You know your usual gcd tricks," she said while stirring her coffee, "but here's a twist — count how often a greatest common divisor is prime. If you can do that quickly, I'll let you grab the first slice of victory pizza."

The team smiled and started typing. Now it's your turn.

You are given two arrays $$$a$$$ and $$$b$$$ of length $$$n$$$. Compute the number of ordered pairs $$$(i, j)$$$ such that $$$1 \le i \le n$$$, $$$1 \le j \le n$$$, and $$$\gcd(a_i, b_j)$$$ is a prime number.

Input

The first line contains a single integer $$$T$$$ $$$(1 \le T \le 10^5)$$$ — the number of test cases.

Each test case consists of the following:

The first line contains a single integer $$$n$$$ $$$(1 \le n \le 10^5)$$$ — the length of both arrays.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ $$$(1 \le a_i \le n)$$$.

The third line contains $$$n$$$ integers $$$b_1, b_2, \dots, b_n$$$ $$$(1 \le b_i \le n)$$$.

It is guaranteed that the sum of all $$$n$$$ over all test cases does not exceed $$$2*10^5$$$.

Output

For each test case, print a single integer — the number of ordered pairs $$$(i,j)$$$ such that $$$\gcd(a_i, b_j)$$$ is a prime.

Examples
Input
5
5
1 3 5 4 4
2 3 2 1 2
2
1 1
2 2
2
1 1
2 2
3
1 2 1
2 2 3
5
4 2 2 5 4
2 1 2 5 3
Output
7
0
0
2
9
Input
5
10
8 6 4 6 9 7 2 3 6 2
6 7 4 6 10 1 6 6 3 3
5
2 3 3 2 2
2 2 3 4 4
4
3 4 1 3
1 2 4 1
3
3 1 1
2 3 2
2
2 1
1 2
Output
47
14
1
1
1