Little Z is bored.

Little Z wants to play games.

Little Z has $N$ new games, where the apparent fun level of the $i$-th game is $w_i$.

Little Z is very picky; he will only play a game if its apparent fun level is an integer multiple of his current excitement level.

Since games can be fun or not, after playing the $i$-th game, Little Z's excitement level will become $e_i$.

Given that Little Z's initial excitement level is $1$, how many games could Little Z potentially play twice?

Input

The first line contains a positive integer $T$, representing the number of test cases, with at most $10$ test cases.

For each test case:

• The first line contains a positive integer $N$, representing the number of games.
• The second line contains $N$ positive integers, where the $i$-th number $w_i$ represents the apparent fun level of the $i$-th game.
• The third line contains $N$ positive integers, where the $i$-th number $e_i$ represents Little Z's excitement level after playing the $i$-th game.

Output

There are $T$ lines in total.

Each line contains a positive integer representing the number of games that Little Z could potentially play twice for the corresponding test case.

Examples

Input 1

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

Output 1

1
3
3
8
5

Subtasks