Little Petya loves looking for numbers' divisors. One day Petya came across the following problem:

You are given $*n*$ queries in the form "$*x*_{*i*}$ $*y*_{*i*}$". For each query Petya should count how many divisors of number $*x*_{*i*}$ divide none of the numbers $*x*_{*i* - *y*_{*i*}}, *x*_{*i* - *y*_{*i*} + 1}, ..., *x*_{*i* - 1}$. Help him.

Input

The first line contains an integer $*n*$ ($1 ≤ *n* ≤ 10^{5}$). Each of the following $*n*$ lines contain two space-separated integers $*x*_{*i*}$ and $*y*_{*i*}$ ($1 ≤ *x*_{*i*} ≤ 10^{5}$, $0 ≤ *y*_{*i*} ≤ *i* - 1$, where $*i*$ is the query's ordinal number; the numeration starts with $1$).

If $*y*_{*i*} = 0$ for the query, then the answer to the query will be the number of divisors of the number $*x*_{*i*}$. In this case you do not need to take the previous numbers $*x*$ into consideration.

Output

For each query print the answer on a single line: the number of positive integers $*k*$ such that

Note

Let's write out the divisors that give answers for the first 5 queries:

1. 1, 2, 4

2. 3

3. 5

4. 2, 6

5. 9, 18