{"id":"494f6875-c4e6-44f4-9a65-b88005845905","name":"Monkey Tradition","description":"In 'MonkeyLand', there is a traditional game called \"Bamboo Climbing\". The rules of the game are as follows:\r\n\r\n1. There are N monkeys who play this game and there are N bamboos of equal heights. Let the height be L meters.\r\n2. Each monkey stands in front of a bamboo and every monkey is assigned a different bamboo.\r\n3. 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.\r\n4. Since they are monkeys, they usually climb by jumping. And in each jump, the ith monkey can jump exactly pi meters (pi 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 ri that he is not able to cover.\r\n5. And before the game, each monkey is assigned a distinct pi.\r\n6. The monkey, who has the lowest ri, wins.\r\n\r\nNow, 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 pi and corresponding ri, but not L. So, you came forward and found the task challenging and so, you want to find L, from the given information.","inputFormat":"Input starts with an integer T, denoting the number of test cases.\r\n\r\nEach case starts with a line containing an integer n. Each of the next n lines contains two integers pi and ri. All pi will be distinct.","outputFormat":"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.","constraints":"T <= 10000\r\n1 <= n <= 12\r\n1 < pi < 40, pi is a prime\r\n0 < ri < pi","sampleCode":{"cpp":{"code":""},"java":{"code":"import java.util.Scanner;\r\n\r\npublic class Main {\r\n public static void main(String[] args) {\r\n //Code Here\r\n }\r\n\r\n\r\n //============EUCLIDS===============//\r\n public static class Pair {\r\n long x;\r\n long y;\r\n long gcd;\r\n\r\n public Pair(long x, long y, long gcd) {\r\n this.x = x;\r\n this.y = y;\r\n this.gcd = gcd;\r\n }\r\n }\r\n\r\n public static Pair euclids(long a, long b) {\r\n if (b == 0) {\r\n return new Pair(1, 0, a);\r\n }\r\n Pair dash = euclids(b, a % b);\r\n\r\n return new Pair(dash.y, dash.x - ((a / b) * dash.y), dash.gcd);\r\n }\r\n}"},"ruby":{"code":""},"python":{"code":""},"javascript":{"code":""}},"points":10,"difficulty":"easy","sampleInput":"2\r\n3\r\n5 4\r\n7 6\r\n11 3\r\n4\r\n2 1\r\n3 2\r\n5 3\r\n7 1","sampleOutput":"Case 1: 69\r\nCase 2: 113\r\n","questionVideo":"","hints":[],"associated":[],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"086949fa-3c5e-40c6-8a9c-f9be4b400318","name":"Number Theory For Experts","slug":"number-theory-for-experts","type":0},{"id":"d17ab8a5-73cd-4d26-9155-82674f8c9cd7","name":"Monkey Tradition","slug":"monkey-tradition","type":1}],"next":null,"prev":{"id":"11157595-ef8a-4538-aecc-f56d867ec34e","name":"Chinese Remainder Theorem","type":1,"slug":"chinese-remainder-theorem"}}}

Monkey Tradition

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 ith monkey can jump exactly pi meters (pi 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 ri that he is not able to cover. 5. And before the game, each monkey is assigned a distinct pi. 6. The monkey, who has the lowest ri, 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 pi and corresponding ri, but not L. So, you came forward and found the task challenging and so, you want to find L, from the given information.

{"id":"494f6875-c4e6-44f4-9a65-b88005845905","name":"Monkey Tradition","description":"In 'MonkeyLand', there is a traditional game called \"Bamboo Climbing\". The rules of the game are as follows:\r\n\r\n1. There are N monkeys who play this game and there are N bamboos of equal heights. Let the height be L meters.\r\n2. Each monkey stands in front of a bamboo and every monkey is assigned a different bamboo.\r\n3. 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.\r\n4. Since they are monkeys, they usually climb by jumping. And in each jump, the ith monkey can jump exactly pi meters (pi 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 ri that he is not able to cover.\r\n5. And before the game, each monkey is assigned a distinct pi.\r\n6. The monkey, who has the lowest ri, wins.\r\n\r\nNow, 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 pi and corresponding ri, but not L. So, you came forward and found the task challenging and so, you want to find L, from the given information.","inputFormat":"Input starts with an integer T, denoting the number of test cases.\r\n\r\nEach case starts with a line containing an integer n. Each of the next n lines contains two integers pi and ri. All pi will be distinct.","outputFormat":"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.","constraints":"T <= 10000\r\n1 <= n <= 12\r\n1 < pi < 40, pi is a prime\r\n0 < ri < pi","sampleCode":{"cpp":{"code":""},"java":{"code":"import java.util.Scanner;\r\n\r\npublic class Main {\r\n public static void main(String[] args) {\r\n //Code Here\r\n }\r\n\r\n\r\n //============EUCLIDS===============//\r\n public static class Pair {\r\n long x;\r\n long y;\r\n long gcd;\r\n\r\n public Pair(long x, long y, long gcd) {\r\n this.x = x;\r\n this.y = y;\r\n this.gcd = gcd;\r\n }\r\n }\r\n\r\n public static Pair euclids(long a, long b) {\r\n if (b == 0) {\r\n return new Pair(1, 0, a);\r\n }\r\n Pair dash = euclids(b, a % b);\r\n\r\n return new Pair(dash.y, dash.x - ((a / b) * dash.y), dash.gcd);\r\n }\r\n}"},"ruby":{"code":""},"python":{"code":""},"javascript":{"code":""}},"points":10,"difficulty":"easy","sampleInput":"2\r\n3\r\n5 4\r\n7 6\r\n11 3\r\n4\r\n2 1\r\n3 2\r\n5 3\r\n7 1","sampleOutput":"Case 1: 69\r\nCase 2: 113\r\n","questionVideo":"","hints":[],"associated":[],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"086949fa-3c5e-40c6-8a9c-f9be4b400318","name":"Number Theory For Experts","slug":"number-theory-for-experts","type":0},{"id":"d17ab8a5-73cd-4d26-9155-82674f8c9cd7","name":"Monkey Tradition","slug":"monkey-tradition","type":1}],"next":null,"prev":{"id":"11157595-ef8a-4538-aecc-f56d867ec34e","name":"Chinese Remainder Theorem","type":1,"slug":"chinese-remainder-theorem"}}}
plane

Editor


Loading...

Monkey Tradition

easy

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 ith monkey can jump exactly pi meters (pi 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 ri that he is not able to cover. 5. And before the game, each monkey is assigned a distinct pi. 6. The monkey, who has the lowest ri, 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 pi and corresponding ri, but not L. So, you came forward and found the task challenging and so, you want to find L, from the given information.

Constraints

T <= 10000 1 <= n <= 12 1 < pi < 40, pi is a prime 0 < ri < pi

Format

Input

Input starts with an integer T, denoting the number of test cases. Each case starts with a line containing an integer n. Each of the next n lines contains two integers pi and ri. All pi will be distinct.

Output

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.

Example

Sample Input

2 3 5 4 7 6 11 3 4 2 1 3 2 5 3 7 1

Sample Output

Case 1: 69 Case 2: 113

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode