#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <stack>
#define sizeTotal 32000
using namespace std;
int main() {
vector<long long>prePrime;
vector<bool> primeGen(sizeTotal + 1, true);
for (int i = 2; i <= sizeTotal; i ++) {
if (primeGen[i]) {
prePrime.push_back(i);
for (int j = i * i; j <= sizeTotal; j += i) {
primeGen[j] = false;
}
}
}
int n;
long long low, high;
cin >> n;
while (n--) {
cout << endl;
cin >> low >> high;
vector<bool>primesInRange(high - low + 1, true);
if (low == 1)
primesInRange[0] = false;
for (long long i : prePrime) {
if (i * i > high)
break;
long long bottom = low / (i * i) * i * i;
if (bottom < low)
bottom += i * i;
for (long long j = bottom; j <= high; j += i) {
primesInRange[j - low] = false;
}
}
for (long long k = 0; k < high - low + 1; k++) {
if (primesInRange[k])
cout << k + low << endl;
}
}
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8dmVjdG9yPgojaW5jbHVkZSA8YWxnb3JpdGhtPgojaW5jbHVkZSA8c3RyaW5nPgojaW5jbHVkZSA8c3RhY2s+CgojZGVmaW5lIHNpemVUb3RhbCAzMjAwMAoKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCmludCBtYWluKCkgewoJdmVjdG9yPGxvbmcgbG9uZz5wcmVQcmltZTsKCXZlY3Rvcjxib29sPiBwcmltZUdlbihzaXplVG90YWwgKyAxLCB0cnVlKTsKCWZvciAoaW50IGkgPSAyOyBpIDw9IHNpemVUb3RhbDsgaSArKykgewoJCWlmIChwcmltZUdlbltpXSkgewoJCQlwcmVQcmltZS5wdXNoX2JhY2soaSk7CgkJCWZvciAoaW50IGogPSBpICogaTsgaiA8PSBzaXplVG90YWw7IGogKz0gaSkgewoJCQkJcHJpbWVHZW5bal0gPSBmYWxzZTsKCQkJfQoJCX0KCX0KCWludCBuOwoJbG9uZyBsb25nIGxvdywgaGlnaDsKCQoJY2luID4+IG47Cgl3aGlsZSAobi0tKSB7CgkJY291dCA8PCBlbmRsOwoJCWNpbiA+PiBsb3cgPj4gaGlnaDsKCQl2ZWN0b3I8Ym9vbD5wcmltZXNJblJhbmdlKGhpZ2ggLSBsb3cgKyAxLCB0cnVlKTsKCQlpZiAobG93ID09IDEpCgkJCXByaW1lc0luUmFuZ2VbMF0gPSBmYWxzZTsKCQlmb3IgKGxvbmcgbG9uZyBpIDogcHJlUHJpbWUpIHsKCQkJCgkJCWlmIChpICogaSA+IGhpZ2gpCgkJCQlicmVhazsKCQkJbG9uZyBsb25nIGJvdHRvbSA9IGxvdyAvIChpICogaSkgKiBpICogaTsKCQkJaWYgKGJvdHRvbSA8IGxvdykKCQkJCWJvdHRvbSArPSBpICogaTsKCQkJZm9yIChsb25nIGxvbmcgaiA9IGJvdHRvbTsgaiA8PSBoaWdoOyBqICs9IGkpIHsKCQkJCXByaW1lc0luUmFuZ2VbaiAtIGxvd10gPSBmYWxzZTsKCQkJfQoJCX0KCQlmb3IgKGxvbmcgbG9uZyBrID0gMDsgayA8IGhpZ2ggLSBsb3cgKyAxOyBrKyspIHsKCQkJaWYgKHByaW1lc0luUmFuZ2Vba10pCgkJCQljb3V0IDw8IGsgKyBsb3cgPDwgZW5kbDsKCQl9CgkJCgkJCgl9CglyZXR1cm4gMDsKfQo=