Problem Description

The RSA Algorithm is an algorithm for public-key cryptography that is based on the presumed difficulty of factoring large integers. Assuming that the Public and Private Keys have already been generated, the RSA algorithm basically consists of the following two operations:
• Encryption: C = PE (mod N)
• Decryption: P = CD (mod N)

where P is a plaintext unit, C is the corresponding ciphertext unit, [E,N] is the Public Key (used for encryption above) and [D,N] is the Private Key (used for decryption).

You will be provided with a ciphertext and the public key used to generate it. Your task is to break the encryption and obtain the private key and the original message.

In case the values of the public and private keys are sufficiently large, it becomes computationally infeasable to perform the operations that you are required to do here. This is the basis for the security provided by this encryption scheme.

Input/Output Specification
• The 1st line of the input consists of a single integer T, which is the number of testcases that follow.
• Each testcase consists of one line, such that the total number of lines in the input file is T+1.
• Each testcase consists of 3 integers on a single line, separated by spaces: E, N and C, as specified above.
• Corresponding to each testcase, output two integers on one line, separated by a space: D and P, as specified above.
• T <= 50, N < 105.

Sample Input

``` 2 17 3233 2790 53 667 511 ```

Sample Output

``` 2753 65 93 549 ```

Problem Setter: Kaustubh Karkare

Languages: C,C++,Java

Time Limit: 1 Second(s)
Score: 100 Point(s)
Input File Limit: 50000 Bytes

Mode Judge

RankNameScore
1xyz0
2Ams0
3TIP0
4team420
5xyzz0
6asdasdasd0
7abcd0
8khankhan0
9Gabriel0
10gigel0