In a faraway number kingdom lived $N$ integers, denoted by an array $a = [a_1, a_2, \dots, a_n] $. Two integers are considered to be related if they have a common divisor larger than $ 1 $. For example, $ 6 $ and $ 9 $ are related (common divisor $ 3 $), but $ 4 $ and $ 15 $ are not.

To rule the kingdom, the king has to accurately understand its population, so he ordered you to carry out a census. The king will give you $Q$ queries, each specifying an integer $x$. For each query, you should count the number of relatives of $x$ in the kingdom.

Input

The first line consists of two integers $ N $ and $ Q $ $ (1 \le N, Q \le 1000) $ — the number of integers and the number of queries.
The second line consists of $N$ integers $ a_1,a_2,\dots,a_n $ $ (2 \le a_i \le 10^9) $ — the integers resided in the kingdom.
The next $Q$ lines each contains an integer $ x $ $ (2 \le x \le 10^9)$ — the integer explained in the statement. Note that $ x $ does not have to be a citizen of the kingdom.

Output

For the $ i $-th query, print the number of relatives of $x$ on the $ i $-th line.