Remainders

All submissions due by 2pm on Friday, April 24.

We know, due to the Chinese remainder theorem, that any two congruence conditions with coprime moduli can be merged into a single congruence condition. In this problem, you will consider the situation where the moduli are not necessarily coprime, and when there are possibly more than two conditions.

You will be given a sequence of congruence conditions. You shoud either find the smallest nonnegative number satisfying all of these congruence conditions, or you should state that the congruence conditions are not consistent with each other. Several examples are shown below.

There will be two primary challenges in solving this problem. First, you should study the proof of the Chinese Remainder Theorem and figure out how to adapt it to the situation when the two moduli may not be coprime (this includes working out how to tell that the conditions are impossible to satisfy simultaneously). Second, for the large input, you will need to learn how to work with very large integers (with hundreds of digits) in the language of your choice. Some comments about this are below.

Input

The first line gives the number of test cases, T. T test cases follow. Each test case begins with a single integer N, the number of congruence conditions. N lines follow, each consisting of two space-separated integers ai mi, which indicate that one congruence condition is that n is congruent to ai modulo mi.

Output

For each test case, print a single line consisting of "Case #X" (where X is the number of the test case) followed by either the word "INCONSISTENT" (if the given congruence conditions are impossible to satisfy simultaneously) or a single integer n, which is the smallest nonnegative integer congruent to ai modulo mi for all i.

Limits

T = 100
0 ≤ ai < mi

Small dataset:
C ≤ 4
mi ≤ 100

Large dataset:
C ≤ 10
mi ≤ 10100

Sample

Input Output
5
2
3 4
4 5
2
15 16
7 24
2
5 8
6 26
5
3 5
4 6
5 7
6 8
7 9
3
151406142 472297165
30 36
5807509 6369883
 Case #1: 19
Case #2: 31
Case #3: INCONSISTENT
Case #4: 2518
Case #5: 32765349597680082

Note that Case 3 is inconsistent because a number which is 5 modulo 8 is odd, while a number that is 6 modulo 26 is even.

Working with large integers

If you attempt the large input, you will need to learn how to work with large integers (with several hundred digits) in the programming language of your choice. If you are coding in Java, you should look up the BigInteger class. In C++, I suggest installing GMP. If you code in Python, this is a nonissue, as Python integers are automatically arbitrary-precision.

Input and output files

Small inputs: 0 1 2 3 4 5 6 7 8 9
Large input: large.in