RSA encryption algorithm which based on prime factorizations of large integers is a asymmetric algorithm. An asymmetric algorithm uses a different key for encrypting or decrypting the message; one of the keys must be kept secret which called secret key, and the other key is usually made public which called public key. So RSA encryption also has a secret key and a public key. But how to get secret key and public key? Here is the answer.

1. We have two pairs of keys:
        public key = (E, N), sender has this key
        secret key = (D, N), receiver has this key
    And we have this amazing conclusion:
        ciphertext = plaintext^E mod N 
        plaintext = ciphertext^D mod N
2. Here are steps to get keys:
    1) get the two big prime number p and q, and N = p*q ;
    2) get the integer L = (p-1)*(q-1);
    3) get the integer E, where 1<E<L and GCD(E, L) = 1; (GCD, Greatest Common Divisor)
    4) get the integer D, where 1<D<L and E*D mod L = 1;
3. Why?
    We know the Euler Theorem:
        if GCD(a, b) = 1, a^phi(b) mod b = 1; (the function phi(x) is euler function of x);
    So if the receiver want to get the plaintext from ciphertext, he can do this:
                      = plaintext
4. The define of the phi(x) is the amount of K:
    where 1<=K<=x and GCD(K, x) = 1;

Now, you get the public key (E, N).
How do you get the secret key (D, N)?
So let's brute force RSA!

first line is the T, means there are T tests; ( 1<=T<=100 )
next T lines, each line includes Ei, Ni; ( 2<=E<=10^6, 2<=N<=10^12 )

output T lines;
each line include the answer Di, Ni of Ei, Ni;

5
974401 501569099893
36581 46714958161
857177 106063763381
724433 233034079387
98853 149852280313

452341087681 501569099893
38956587221 46714958161
95253670889 106063763381
171607017881 233034079387
34970286381 149852280313