SP28413 ADAFENCE - Ada and Fence

Ada 拥有一块圆形的土地。她想用篱笆把它围起来。不管怎样，因为没有人卖圆木板，她决定用篱笆把它围成普通的 $k$ 形。问题是，只有有限的数量或地方（在圆上）可以建造桩柱。Ada 要求你找出在她的土地上可以建造的不同的规则 $k$ 形围栏的数量（如果两个 $k$ 形围栏没有共用的柱子，则认为它们是不同的）。

第一行输入 $T$ ，表示有 $T$ 组数据。 接下来是 $T$ 组数据，每组数据以两个整数 $3,3$ 开头，可以构建支柱的地方的数量和规则 $k$ 形边的数量 其后是一条 $N$ 整数为 $1$ 的直线，表示可以在两个连续点之间建立支柱的弧长。所有长度之和都可以被 $k$ 整除。 所有测试用例的N之和不超过 $2\times {10}^{6}$

对于每组数据，输出可以构建的不同规则 $k$ 形栅栏的数量。