CF111B.Petya and Divisors

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-yi},x_{i-yi}+1,...,x_{i-1}$ . Help him.

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.

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

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