## 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 b_{i}, p_{i} and c_{i} (0≤b_{i}≤100, 2≤p_{i}<1,000,000,000, 0<c_{i}≤30, 0≤i≤k), where p_{i} is a prime number, p_{i} are all distinct and b_{i}<p_{i}^{ci}. 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