$N$ people are standing in a row. Each of them has been assigned a rating of $x$ and a range value $y$. A person with a range value of $y$ has access to ratings of the first $y$ person standing in front of him.

For each person, determine the count of unique prime factors of his or her rating $x$ that divides any of the ratings of the person standing in his range.

Note: For each person, their range value is always less than or equal to the number of people standing in front of him.

Input format

• The first line contains an integer $N$ denoting the number of people in a row.
• The second line consists of $N$ space-separated integers denoting the ratings of people in the row.
• The third line consists of $N$ space-separated integers denoting the range values of people in a row.

Output format

For each person, print the count of unique prime factors of his or her rating $x$ that divides any of the ratings of the person standing in his or her range.

Constraints

$1 \le N \le 100\\ 1 \le x \le 100\\ 0 \le y < i\\ 1 \le i \le N$