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

You are given n queries in the form "xi yi". For each query Petya should count how many divisors of number xi divide none of the numbers xi - yi, xi - yi + 1, ..., xi - 1. Help him.

Input

The first line contains an integer n (1 ≤ n ≤ 105). Each of the following n lines contain two space-separated integers xi and yi (1 ≤ xi ≤ 105, 0 ≤ yi ≤ i - 1, where i is the query's ordinal number; the numeration starts with 1). 

If yi = 0 for the query, then the answer to the query will be the number of divisors of the number xi. 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 <image>

Examples

Input

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


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
import java.util.List;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.ArrayList;
import java.util.Comparator;
import java.io.BufferedReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.math.BigInteger;
import java.util.HashSet;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 * @author AlexFetisov
 */
public class Main {
	public static void main(String[] args) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		InputReader in = new InputReader(inputStream);
		PrintWriter out = new PrintWriter(outputStream);
		TaskB solver = new TaskB();
		solver.solve(1, in, out);
		out.close();
	}
}

class TaskB {

    final static int BLOCK_SIZE = 333;
    private HashSet<Integer>[] sets;
    private HashSet<Integer>[] setForUnit;
    private int[] blockLeftPosition;
    private int[] blockRightPosition;
    private int[] inBlock;
    private int number_of_blocks;
    int[] prev;

    public void solve(int testNumber, InputReader in, PrintWriter out) {
        int n = in.nextInt();
        number_of_blocks = (n + BLOCK_SIZE - 1) / BLOCK_SIZE;
        blockLeftPosition = new int[number_of_blocks];
        blockRightPosition = new int[number_of_blocks];
        inBlock = new int[n];
        prev = new int[100001];
        Arrays.fill(prev, -1);
        for (int i = 0, j = BLOCK_SIZE-1, id = 0; i < n; i += BLOCK_SIZE, j += BLOCK_SIZE, ++id) {
            int left = i;
            int right = Math.min(j, n-1);
            blockLeftPosition[id] = left;
            blockRightPosition[id] = right;
            for (int p = left; p <= right; ++p) {
                inBlock[p] = id;
            }
        }


        sets = new HashSet[number_of_blocks];
        setForUnit = new HashSet[n];
        for (int i = 0; i < number_of_blocks; ++i) {
            sets[i] = new HashSet<Integer>();
        }


        for (int i = 0; i < n; ++i) {
            int X = in.nextInt();
            int Y = in.nextInt();
            int left = i - Y;
            int right = i - 1;

            setForUnit[i] = getDivisors(X);
            if (prev[X] >= left) {
                for (int x : setForUnit[i]) {
                    sets[inBlock[i]].add(x);
                }
                out.println(0);
                prev[X] = i;
                for (int x : setForUnit[i]) {
                    prev[x] = i;
                }
                continue;
            }
            HashSet<Integer> newDivs = new HashSet<Integer>(setForUnit[i]);
            for (int x : setForUnit[i]) {
                if (prev[x] >= left) {
                    newDivs.remove(x);
                }
            }
            prev[X] = i;
            for (int x : setForUnit[i]) {
                prev[x] = i;
            }
            //int res = calc(left, right, newDivs);
            int res = newDivs.size();
            out.println(res);
            for (int x : setForUnit[i]) {
                sets[inBlock[i]].add(x);
            }
        }
    }

    private HashSet<Integer> getDivisors(int x) {
        List<Long> d = IntegerUtils.getDivisors(x);
        HashSet<Integer> r = new HashSet<Integer>(d.size());
        for (int i = 0; i < d.size(); ++i) {
            r.add((int) d.get(i).longValue());
        }
        return r;
    }
}

class InputReader {
    private BufferedReader reader;
    private StringTokenizer stt;

    public InputReader(InputStream stream) {
        reader = new BufferedReader(new InputStreamReader(stream));
    }

    public String nextLine() {
        try {
            return reader.readLine().trim();
        } catch (IOException e) {
            return null;
        }
    }

    public String nextString() {
        while (stt == null || !stt.hasMoreTokens()) {
            stt = new StringTokenizer(nextLine());
        }
        return stt.nextToken();
    }

    public int nextInt() {
        return Integer.parseInt(nextString());
    }

}

class IntegerUtils {

    public static List<Pair<Long, Integer>> factorize(long number) {
        List<Pair<Long, Integer>> result = new ArrayList<Pair<Long, Integer>>();
        for (long i = 2; i * i <= number; i++) {
            if (number % i == 0) {
                int power = 0;
                do {
                    power++;
                    number /= i;
                } while (number % i == 0);
                result.add(Pair.makePair(i, power));
            }
        }
        if (number != 1) {
            result.add(Pair.makePair(number, 1));
        }
        return result;
    }

    public static List<Long> getDivisors(long number) {
        List<Pair<Long, Integer>> primeDivisors = factorize(number);
        return getDivisorsRec(primeDivisors, 0, 1, new ArrayList<Long>());
    }

    private static List<Long> getDivisorsRec(List<Pair<Long, Integer>> primeDivisors, int index, long current, List<Long> result) {
        if (index == primeDivisors.size()) {
            result.add(current);
            return result;
        }
        long p = primeDivisors.get(index).first;
        int power = primeDivisors.get(index).second;
        for (int i = 0; i <= power; i++) {
            getDivisorsRec(primeDivisors, index + 1, current, result);
            current *= p;
        }
        return result;
    }

}

class Pair<U, V> implements Comparable<Pair<U, V>> {
    public final U first;
    public final V second;

    public static<U, V> Pair<U, V> makePair(U first, V second) {
        return new Pair<U, V>(first, second);
    }

    public Pair(U first, V second) {
        this.first = first;
        this.second = second;
    }

    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;

        Pair pair = (Pair) o;

        return !(first != null ? !first.equals(pair.first) : pair.first != null) && !(second != null ? !second.equals(pair.second) : pair.second != null);

    }

    public int hashCode() {
        int result = first != null ? first.hashCode() : 0;
        result = 31 * result + (second != null ? second.hashCode() : 0);
        return result;
    }

    public String toString() {
        return "(" + first + "," + second + ")";
    }

    public int compareTo(Pair<U, V> o) {
        int value = ((Comparable<U>)first).compareTo(o.first);
        if (value != 0)
            return value;
        return ((Comparable<V>)second).compareTo(o.second);
    }
}

