#include "testlib.h"

const int N_MAX = 1e5, M_MAX = 40009;
int main(){
    registerValidation();
    const int N = inf.readInt(2, N_MAX);
    inf.readSpace();
    const int M = inf.readInt(2, M_MAX);
    inf.readEoln();
    for(int i = 2; i * i <= M; i++) ensure(M % i);
    for(int i = 0; i < N; i++){
        inf.readInt(0, M - 1);
        inf.readSpace();
        inf.readInt(1, M - 1);
        inf.readEoln();
    }
    inf.readEof();
}