提示: 欢迎访问OurACM平台。
Problem 1971 A math problem

Accept: 49    Submit: 190
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

There is a math problem, which is showed as follows:

(1) Find the smallest positive integer N that satisfies the following k+1 equations, we guarantee that N is no larger than 1,000,000,000.
(2) Calculate , we guarantee that M is no larger than 1,000,000,000. (3) Calculate , where A is a given integer. (4) Print the Ans.

Input

The first line of the input contains an integer T (T≤20), indicating the number of cases. Each case begins with a line containing two integers A (50≤A≤1,000,000,000) and k (0≤k≤20). Each of the following k+1 lines contains three integers bi, pi and ci (0≤bi≤100, 2≤pi<1,000,000,000, 0<ci≤30, 0≤i≤k), where pi is a prime number, pi are all distinct and bi<pici. We guarantee that a valid N always exists.

Output

For each test case, print a line containing the test case number (beginning with 1) and the answer you calculated.

Sample Input

2 50 0 0 2 1 50 1 1 2 1 2 3 1

Sample Output

Case 1: 1 Case 2: 1

Source

The 35th ACM/ICPC Asia Regional Fuzhou Site —— Online Contest

Submit  Back  Status  Discuss