20038 - Helping Cicada

蝉是一种昆虫，有着透明的大眼睛和脉络清晰的翅膀，类似于“罐蝇”。据认为，这些昆虫是在180万年前的更新世时期进化而来的。全世界大约有2500种蝉，生活在温带和热带气候地区。

它们都是刺吸式昆虫，用尖锐的口器刺穿植物并吸出汁液。但也有一些捕食者（比如鸟类、蝉杀手黄蜂）会攻击蝉。每种捕食者都有一个攻击蝉的周期性循环。例如，鸟类每3年攻击一次；黄蜂每2年攻击一次。因此，如果蝉在第12年出现，那么鸟类或黄蜂就可以攻击它们。如果它们在第7年出现，那么就没有捕食者会攻击它们。

所以，首先它们会选择一个数字 N，表示可能的生命周期长度。然后会有一个整数 M，表示捕食者的总数。接下来的 M 个整数表示每种捕食者的生命周期。在 1 到 N 范围内，不能被任何这 M 个生命周期数整除 的年份，将被视为蝉的安全出土年份。你需要帮助它们计算这样的年份有多少个。

第一行是一个整数 T（T \le 125），表示测试用例的数量。

每个测试用例包含两个整数 N（1 \le N < 2^{31}）和 M（1 \le M \le 15）。下一行包含 M 个正整数（适合 32 位有符号整数），表示每个捕食者的生命周期。

对于每个测试用例，输出一行，格式为 Case x: y，其中 x 是测试用例编号（从 1 开始），y 是蝉的安全出土年份的数量。