KPRIMESB - Almost Prime Numbers Again

no tags 

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 ≤ 106) 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

hide comments
HM Mehrab: 2016-04-01 19:16:31

I can't come up with an efficient solution to those constraints. If you want those constraints, you'll have to make the problem yourself lol

Last edit: 2016-04-01 21:50:28
mehmetin: 2016-04-01 18:42:56

A still harder version is possible (for example N<=10^9, K<=1000, T and time limit can be chosen accordingly)


Added by:HM Mehrab
Date:2016-04-01
Time limit:0.5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY