#include <cstdio>

long long pre[2000005], n, a, b, licz;
bool tablica[2000005];

int main()
{
    for (int i = 2; i <= 2000000; i++)
    {
        tablica[i] = true;
    }
    for(int i = 2; i <= 2000000; i++)
        if (tablica[i])
            for(int j = 2 * i; j <= 2000000; j = j + i)
                tablica[j] = false;
    for (int i = 0; i <= 2000000; i++)
    {
        if (tablica[i] == true)
            licz += i;
        pre[i] = licz;
    }
    scanf("%lld", &n);
    for (int i = 0; i <= n; i++)
    {
        scanf("%lld%lld", &a, &b);
        if (tablica[a] == true)
            printf("%lld\n", pre[b] - pre[a - 1]);
        else
            printf("%lld\n", pre[b] - pre[a]);
    }
    getchar();
    getchar();
    return 0;
}