Time Limit: 2 second(s) | Memory Limit: 32 MB |
In 'MonkeyLand', there is a traditional game called "Bamboo Climbing". The rules of the game are as follows:
1) There are N monkeys who play this game and there are N bamboos of equal heights. Let the height be L meters.
2) Each monkey stands in front of a bamboo and every monkey is assigned a different bamboo.
3) When the whistle is blown, the monkeys start climbing the bamboos and they are not allowed to jump to a different bamboo throughout the game.
4) Since they are monkeys, they usually climb by jumping. And in each jump, the i^{th} monkey can jump exactly p_{i} meters (p_{i} is a prime). After a while when a monkey finds that he cannot jump because one more jump may get him out of the bamboo, he reports the remaining length r_{i} that he is not able to cover.
5) And before the game, each monkey is assigned a distinct p_{i}.
6) The monkey, who has the lowest r_{i}, wins.
Now, the organizers have found all the information of the game last year, but unluckily they haven't found the height of the bamboo. To be more exact, they know N, all p_{i} and corresponding r_{i}, but not L. So, you came forward and found the task challenging and so, you want to find L, from the given information.
Input starts with an integer T (≤ 10000), denoting the number of test cases.
Each case starts with a line containing an integer n (1 ≤ n ≤ 12). Each of the next n lines contains two integers p_{i} (1 < p_{i} < 40, p_{i} is a prime) and r_{i} (0 < r_{i} < p_{i}). All p_{i} will be distinct.
For each case, print the case number and the minimum possible value of L that satisfies the above conditions. If there is no solution, print 'Impossible'.
Sample Input |
Output for Sample Input |
2 3 5 4 7 6 11 3 4 2 1 3 2 5 3 7 1 |
Case 1: 69 Case 2: 113 |
Developed and Maintained by
JANE ALAM JAN |
Copyright © 2012
LightOJ, Jane Alam Jan |