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⁵). Each of the following n lines contain two space-separated integers x_i and y_i (1 ≤ x_i ≤ 10⁵, 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 $\text{[math]}$

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

Petya and Divisors

Examples