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.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;

public class Main implements Runnable {

    long gcd(long a, long b) {
        while (a != 0 && b != 0) {
            if (a > b)
                a %= b;
            else
                b %= a;
        }
        return a + b;
    }
    class Summator {

        long[] arr;

        int n;
        int delta;

        public Summator(int n) {
            this.n = n;
            int p;
            for(p = 2; p < n; p *= 2) { }
            arr = new long[p * 2 - 1];
            delta = p - 1;
        }

        public long get(int id) {
            id += delta;
            return arr[id];
        }

        int up(int id) {
            return (id - 1) / 2;
        }

        int left(int a) {
            return a * 2 + 1;
        }

        int right(int a) {
            return a * 2 + 2;
        }

        public void set(int id, long val) {
            id += delta;
            arr[id] = val;
            while (true) {
                id = up(id);
                arr[id] = gcd(arr[left(id)], arr[right(id)]);
                if (id == 0) break;
            }
        }

        public long get(int from, int to) {
            from += delta;
            to += delta;
            long ans = 0;
            while (from < to) {
                if (from % 2 == 0) {
                    ans = gcd(ans, arr[from]);
                    from++;
                }
                if (to % 2 == 1) {
                    ans = gcd(ans, arr[to]);
                    to--;
                }
                from = up(from);
                to = up(to);
            }
            if (from == to) ans = gcd(ans, arr[from]);
            return ans;
        }
    }

    boolean ok(List<Integer> lst, int from, int to) {
        int idx = Collections.binarySearch(lst, from);
        if (idx < 0) idx = -idx - 1;
        idx = Math.max(idx, 0);
        while (idx < lst.size() && lst.get(idx) < from)
            idx++;
        return idx < lst.size() && lst.get(idx) >=from && lst.get(idx) <= to;
    }


    public void solve() throws IOException {
        final int MX = 100000;
        int n = nextInt();
        int[] xs = new int[n];
        int[] ys = new int[n];
        List<Integer>[] dvs = new List[MX + 1];
        for(int i = 0; i <= MX; ++i)
            dvs[i] = new ArrayList<Integer>();
        for(int i = 0; i < n; ++i) {
            xs[i] = nextInt();
            ys[i] = nextInt();
            int x = xs[i];
            for(int j = 1; j * j <= x; ++j) {
                if (x % j == 0) {
                    dvs[j].add(i + 1);
                    if (j * j != x)
                        dvs[x / j].add(i + 1);
                }
            }
        }

        for(int i = 0; i < n; ++i) {
            int x = xs[i], y = ys[i];
            int ans = 0;
            for(int j = 1; j * j <= x; ++j) {
                if (x % j == 0) {
                    if (y == 0 || !ok(dvs[j], i - y + 1, i))
                        ans++;
                    if (j * j != x) {
                        if (y == 0 || !ok(dvs[x / j], i - y + 1, i))
                            ans++;
                    }
                }
            }
            pw.println(ans);
        }
    }

    static final String filename = "A";
    static final boolean fromConsole = true;
    
    public void run() {
        try {
            if (!fromConsole) {
                in = new BufferedReader(new FileReader(filename + ".in"));
                pw = new PrintWriter(filename + ".out");
            } else {
                in = new BufferedReader(new InputStreamReader(System.in));
                pw = new PrintWriter(System.out);
            }
            st = new StringTokenizer("");
            long st = System.currentTimeMillis();
            solve();
            //pw.printf("\nWorking time: %d ms\n", System.currentTimeMillis() - st);
            pw.close();
        } catch (Exception e) {
            e.printStackTrace();
            System.exit(-1);
        }
    }
    
    private StringTokenizer st;
    private BufferedReader in;
    private PrintWriter pw;
    
    boolean hasNext() throws IOException {
        while (!st.hasMoreTokens()) {
            String line = in.readLine();
            if (line == null) {
                return false;
            }
            st = new StringTokenizer(line);
        }
        return st.hasMoreTokens();
    }
    
    String next() throws IOException {
        return hasNext() ? st.nextToken() : null;
    }
    
    int nextInt() throws IOException {
        return Integer.parseInt(next());
    }
    
    BigInteger nextBigInteger() throws IOException {
        return new BigInteger(next());
    }
    
    long nextLong() throws IOException {
        return Long.parseLong(next());
    }
    
    double nextDouble() throws IOException {
        return Double.parseDouble(next());
    }
    
    public static void main(String[] args) {
        new Thread(new Main()).start();
    }
}
