蝉是一种昆虫，有着透明的大眼睛和脉络清晰的翅膀，类似于“罐蝇”。据认为，这些昆虫是在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$ 是蝉的安全出土年份的数量。