Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official.
×

Package for this problem was not updated by the problem writer or Codeforces administration after we’ve upgraded the judging servers. To adjust the time limit constraint, solution execution time will be multiplied by 2. For example, if your solution works for 400 ms on judging servers, then value 800 ms will be displayed and used to determine the verdict.

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

A. Bicycle Chain

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputVasya's bicycle chain drive consists of two parts: *n* stars are attached to the pedal axle, *m* stars are attached to the rear wheel axle. The chain helps to rotate the rear wheel by transmitting the pedal rotation.

We know that the *i*-th star on the pedal axle has *a*_{i} (0 < *a*_{1} < *a*_{2} < ... < *a*_{n}) teeth, and the *j*-th star on the rear wheel axle has *b*_{j} (0 < *b*_{1} < *b*_{2} < ... < *b*_{m}) teeth. Any pair (*i*, *j*) (1 ≤ *i* ≤ *n*; 1 ≤ *j* ≤ *m*) is called a gear and sets the indexes of stars to which the chain is currently attached. Gear (*i*, *j*) has a gear ratio, equal to the value .

Since Vasya likes integers, he wants to find such gears (*i*, *j*), that their ratios are integers. On the other hand, Vasya likes fast driving, so among all "integer" gears (*i*, *j*) he wants to choose a gear with the maximum ratio. Help him to find the number of such gears.

In the problem, fraction denotes division in real numbers, that is, no rounding is performed.

Input

The first input line contains integer *n* (1 ≤ *n* ≤ 50) — the number of stars on the bicycle's pedal axle. The second line contains *n* integers *a*_{1}, *a*_{2}, ..., *a*_{n} (1 ≤ *a*_{i} ≤ 10^{4}) in the order of strict increasing.

The third input line contains integer *m* (1 ≤ *m* ≤ 50) — the number of stars on the rear wheel axle. The fourth line contains *m* integers *b*_{1}, *b*_{2}, ..., *b*_{m} (1 ≤ *b*_{i} ≤ 10^{4}) in the order of strict increasing.

It is guaranteed that there exists at least one gear (*i*, *j*), that its gear ratio is an integer. The numbers on the lines are separated by spaces.

Output

Print the number of "integer" gears with the maximum ratio among all "integer" gears.

Examples

Input

2

4 5

3

12 13 15

Output

2

Input

4

1 2 3 4

5

10 11 12 13 14

Output

1

Note

In the first sample the maximum "integer" gear ratio equals 3. There are two gears that have such gear ratio. For one of them *a*_{1} = 4, *b*_{1} = 12, and for the other *a*_{2} = 5, *b*_{3} = 15.

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/14/2018 07:35:57 (d2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|