Recently, the bear started studying data structures and faced the following problem.

You are given a sequence of integers *x*<sub class="lower-index">1</sub>, *x*<sub class="lower-index">2</sub>, ..., *x*<sub class="lower-index">*n*</sub> of length *n* and *m* queries, each of them is characterized by two integers *l*<sub class="lower-index">*i*</sub>, *r*<sub class="lower-index">*i*</sub>. Let's introduce *f*(*p*) to represent the number of such indexes *k*, that *x*<sub class="lower-index">*k*</sub> is divisible by *p*. The answer to the query *l*<sub class="lower-index">*i*</sub>, *r*<sub class="lower-index">*i*</sub> is the sum: <img align="middle" class="tex-formula" src="https://espresso.codeforces.com/5e448f6c1a0e40843cecdbbeb95970464626032f.png" style="max-width: 100.0%;max-height: 100.0%;"/>, where *S*(*l*<sub class="lower-index">*i*</sub>, *r*<sub class="lower-index">*i*</sub>) is a set of prime numbers from segment [*l*<sub class="lower-index">*i*</sub>, *r*<sub class="lower-index">*i*</sub>] (both borders are included in the segment).

Help the bear cope with the problem.
The first line contains integer *n* (1 ≤ *n* ≤ 10<sup class="upper-index">6</sup>). The second line contains *n* integers *x*<sub class="lower-index">1</sub>, *x*<sub class="lower-index">2</sub>, ..., *x*<sub class="lower-index">*n*</sub> (2 ≤ *x*<sub class="lower-index">*i*</sub> ≤ 10<sup class="upper-index">7</sup>). The numbers are not necessarily distinct.

The third line contains integer *m* (1 ≤ *m* ≤ 50000). Each of the following *m* lines contains a pair of space-separated integers, *l*<sub class="lower-index">*i*</sub> and *r*<sub class="lower-index">*i*</sub> (2 ≤ *l*<sub class="lower-index">*i*</sub> ≤ *r*<sub class="lower-index">*i*</sub> ≤ 2·10<sup class="upper-index">9</sup>) — the numbers that characterize the current query.
#include <iostream>
/// 385C
using namespace std;

const int dim = 1e7+1;

int prim[dim], frecv[dim], cati_multipli[dim];

int main()
{

    int n, q, i, j, nr, st, dr;
    cin >> n;
    for (i = 1; i <= n; ++i)
    {
        cin >> nr;
        ++frecv[nr];
        if (nr % 2 == 0)
            ++cati_multipli[2];
    }

    for (i = 3; i < dim; i = i + 2)
    {
        if (prim[i] == 0)
        {
            for (j = i; j < dim; j = j + i)
            {
                prim[j] = 1;
                cati_multipli[i] = cati_multipli[i] + frecv[j];
            }
            prim[i] = 0;
        }
    }

    for (i = 1; i < dim; ++i)
        cati_multipli[i] = cati_multipli[i - 1] + cati_multipli[i];

    cin >> q;

    for (i = 1; i <= q; ++i)
    {
        cin >> st >> dr;
        if (st >= dim)
            st = dim - 1;
        if (dr >= dim)
            dr = dim - 1;
        cout << "rasp: " << cati_multipli[dr] - cati_multipli[st - 1] << endl;
    }
    return 0;
}
