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.

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 **a _{i} m_{i}**, which indicate that one congruence condition is that

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 **a _{i}** modulo

0 ≤

Small dataset:

**C** ≤ 4

**m _{i}** ≤ 100

Large dataset:

**C** ≤ 10

**m _{i}** ≤ 10

Input | Output |

52 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: 19Case #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.

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.

Large input: large.in