Almost Prime Numbers are composite numbers which are not divisible by certain prime numbers. Given K prime numbers and an integer N, find out the number of Almost Prime Numbers (i.e. composite numbers not divisible by any of the given K prime numbers) that are not greater than N.

Input

First line of input consists of an integer T (1 ≤ T ≤ 1000), denoting the number of test cases. Then T test cases follow. Each case begins with a line containing two integers N (0 ≤ N ≤ 10⁶) and K (1 ≤ K ≤ 10). The next line contains K space separated prime numbers. All the prime numbers are guaranteed to be less than 50.

Output

For each test case, output a single line in the format Case X: Y, where X denotes the test case number and Y denotes the number of Almost Prime Numbers that are not greater than N.

Example

Input:
2
1000 3
2 3 5
49 3
2 3 5

Output:
Case 1: 100
Case 2: 1