有 $m$ 块石头围成一个圆圈，有 $n$ 只青蛙在上面跳跃。石头编号从 $0$ 到 $m-1$，青蛙编号从 $1$ 到 $n$。第 $i$ 只青蛙单次跳跃的距离恰好为 $a_i$ 块石头，这意味着它能从石头 $j \pmod m$ 跳到石头 $(j + a_i) \pmod m$（因为所有石头都在圆圈上）。

所有青蛙都从石头 $0$ 开始跳跃，每只青蛙都可以跳任意多次。青蛙到达某块石头时即视为占据了该石头，它会不断跳跃以占据尽可能多的石头。即使青蛙跳走后，石头仍被视为“已占据”。它们想知道哪些石头可以被至少一只青蛙占据。由于石头数量可能非常多，青蛙们只想知道这些被占据石头的编号之和。

输入格式

输入包含多组测试数据（不超过 $20$ 组），第一行包含一个整数 $t$，表示测试数据的总数。

对于每组测试数据，第一行包含两个正整数 $n$ 和 $m$，分别表示青蛙的数量和石头的数量（$1 \le n \le 10^4$，$1 \le m \le 10^9$）。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，其中 $a_i$ 表示第 $i$ 只青蛙的跳跃步长（$1 \le a_i \le 10^9$）。

输出格式

对于每组测试数据，首先打印测试数据的编号，然后打印所有被占据石头的编号之和。

样例

输入 1

3
2 12
9 10
3 60
22 33 66
9 96
81 40 48 32 64 16 96 42 72

输出 1

Case #1: 42
Case #2: 1170
Case #3: 1872