$$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