Description

Little z is very bored.

Little z wants to play games.

Little z has $N$ new games. The apparent fun level of the $i$-th game is $w_i$.

Little z is picky. He will only play a game whose apparent fun level is an integer multiple of his excitement level.

Since some games are actually fun and some are not, after finishing the $i$-th game, Little z’s excitement level will become $e_i$.

It is known that Little z’s initial excitement level is $1$. Please determine how many games Little z might play twice.

Input Format

The first line contains a positive integer $T$, indicating the number of testdata groups, up to $10$ groups.

For each group of testdata:

• The first line contains a positive integer $N$, indicating the number of games.
• The second line contains $N$ positive integers. The $i$-th number $w_i$ indicates that the apparent fun level of the $i$-th game is $w_i$.
• The third line contains $N$ positive integers. The $i$-th number $e_i$ indicates that after Little z finishes the $i$-th game, his excitement level will become $e_i$.

Output Format

Output $T$ lines in total.

Each line contains one positive integer, indicating for the corresponding testdata group, the number of games that Little z might play twice.

5
1
100000
100000
5
1 2 6 15 35
5 7 9 2 3
5
2 3 5 35 21
7 11 7 3 2
10
6 15 77 12 24 37 35 99 55 42
4 2 5 7 11 3 6 8 9 10
10
6540 5604 567 57065 60 670 6870 1230 465 6540
12 5 37 3 34 13 17 18 10 12

1
3
3
8
5

Hint

Explanation for Sample 2

Numbers represent game indices, and arrows indicate the next one.

• Case $1$: $2\to 5\to 4\to 2$.
• Case $2$: $5\to 4\to 2\to 5$.
• Case $3$: $4\to 2\to 5\to 4$.

So Little z might play games $2,4,5$ twice.

No matter what, Little z cannot play game $1$ or $3$ twice.

Constraints

Translated by ChatGPT 5