Petya and Divisors

Description:

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

Sample Input:

6
4 0
3 1
5 2
6 2
18 4
10000 3

Sample Output:

3
1
1
2
2
22

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