Code Breakers

It is almost certain that the NSA intercepts and logs, and probably analyzes, much of the e-mail traffic in the world, and certainly in the US. One way organizations and individuals protect the privacy of their messages is encryption, and one of the cooler ideas in encryption is public key encryption. Roughly, it goes like this. You publish one key, so everyone can see it and use it to encrypt a message to you. Decrypting that message takes a different key, which only you know. The idea sounds nice, and the far bigger contribution was showing that it is actually mathematically possible, which is what the RSA algorithm did.

Here is how it works. You choose two prime numbers $p$ and $q$ (usually at random, though that does not matter for this problem). Your public key, which everyone can see, consists of the number $n = p \times q$ and a small number $e$. Your private key, which only you should know, is a number $d \le (p-1)(q-1)$ such that $(d \times e) \bmod ((p-1)(q-1)) = 1$. If you know $p$ and $q$, finding such a $d$ is easy. If you do not, it seems difficult, and that is why only you, the owner of $p$ and $q$, can decrypt the message.

Now, how to encrypt and decrypt a message. Say the message is a number $m$ (any string becomes a number by reading its bits as one). The encrypted version is $c = m^e \bmod n$, which anyone can compute from $n$ and $e$ alone. To decrypt, the recipient computes $c^d \bmod n$, which recovers the original message.

To break someone's key, it is enough to factor $n$ and recover $p$ and $q$. This is believed, though not proved, to be hard as long as $p$ and $q$ are large enough (thousands of digits). If they are too small, brute force breaks RSA. That is what you will do here.

The R, S and A in RSA come from the surnames Rivest, Shamir and Adleman.

The first line contains the number $K$ of data sets. Each of the next $K$ lines holds one data set as three integers $n$, $e$, $c$ separated by spaces, with $5 \le n \le 10^9$, $1 \le e \le 10000$ and $1 \le c < n$. In other words, the attacker knows the public key and the encrypted message. In these inputs $n$ is always a product of exactly two primes, and $e$ is always given so that a $d$ satisfying the condition above exists.

For each data set, print Data Set x: on a line by itself, where $x$ is its number. Then print the decrypted message $m$ of the ciphertext $c$ on a line by itself, followed by an empty line.