Dk

#include <stdio.h>
#define len 3

const short base[len] = {2, 7, 61};
int total;

inline int logpow(long long bs, int ex, const int mod)
{
    long long res = 1;
    while (ex) {
        if (ex & 1) {
            res = res * bs % mod;
            --ex;
        }
        bs = bs * bs % mod;
        ex >>= 1;
    }
    return (int)res;
}

inline short process(int nr)
{
    short tmp, i, s, a;
    int aux = 1, d;
    --nr;
    for (i = 0; aux <= nr; ++i) {
        if (!(nr % aux)) {
            s = i;
            d = nr / aux;
        }
        aux <<= 1;
    }
    //fprintf(stderr, "%d %d\n", s, d);
    for (i = 0; i < len; ++i) {
        a = base[i];
        aux = logpow(a, d, nr + 1);
        //fprintf(stderr, "%d %d\n", a, aux);
        if (aux != 1 && aux != nr) {
            for (tmp = 0; tmp < s; ++tmp) {
                if (aux == s) {
                    return 0;
                }
                aux = logpow(aux, 2, nr + 1);
                if (aux == 1) {
                    return 0;
                } else if (aux == nr) {
                    break;
                }
            }
        }
    }
    return 1;
}

int main()
{
    short n;
    int a, b;
    freopen("print.in", "rt", stdin);
    for (scanf("%hd", &n); n; --n) {
        scanf("%d %d", &a, &b);
        if (a == 2) {
            puts("2");
            ++a;
        }
        if (a == 3 && a <= b) {
            puts("3");
            a += 2;
        }
        if (!(a & 1)) {
            ++a;
        }
        while (a <= b) {
            if (process(a)) {
                printf("%d\n", a);
            }
            a += 2;
        }
    }
    return 0;
}