Problem 1239
God Created The Integers
Time Limit: 1000ms
Memory Limit: 65536kb
“God created the integers, while the rest is the work of man” is a famous remark on mathematics by Kronecker, a famous mathematician. People understand numbers gradually through the process of solving equations. A very long time ago, people only know the integers Z. In order to let the equation 2x+1=0 has a solution, they introduce the notion of rational numbers Q. Later, man find that there is quite a lot situation requiring the solvability of equations x^2=0, which leads to the emergence of real numbers R. Finally, people import the concept of complex numbers C to make any polynomial has a zero point.

Number theory is a centuries-old subject focusing its attention on the theory of integers. There are many beautiful theorems and methods in number theory. As with everything else, so with the number theory: beauty can be perceived, but not explained. In this problem, we will try to solve an interesting one.

Mathematicians also try to solve equations in number theory, but here they do it in a different way. For example, they find quadratic equations x^a ≡0(mod b) is of special importance. As you can see, the operation related here is taken in the modular form. If you are familiar with number theory, you will find that we only need to consider the situation where b is a prime through the famous Chinese Remainder Theorem.

Now, let us consider the equation x^2≡ t(mod p) where p is a prime. Unfortunately, not any t can guarantee the existence of b satisfying b^2≡t(mod p). It is important to find the condition of t guaranteeing the solvability. But as you know, this problem is a little difficult and thus let us try to solve a little easier problem related.

Let p be a prime and p 1(mod 4). You are asked to calculate:

where [a] denotes the largest integer not larger than a. Since sp can be quite large and as a lover of number theory, you are required to calculate its reverse with respect to p, namely, the number rp satisfying 0 < rp < p and rpsp≡1(mod p).
The first line contains a number T ≤ 200, which indicates the number of test case.
Then in follows T lines, each line is a prime number p. 10<p< 4 *10^8, p≡1( mod 4 ).
For each test case, output one line containing "Case #x: y", where x is the case number (starting from 1) and y is rp.
Sample Input
Sample Output
Case #1: 15
Case #2: 28
University of Science and Technology of China
Online Judge for ACM/ICPC
Processed in 1.2ms with 1 query(s).