题目内容

给定一个长度为 $n$ 的整数序列 $a_1,a_2,\dots,a_n$，视为环状序列（位置 $n$ 的后继为位置 $1$）。给定正整数 $M$，对于每个起点 $s \;(1 \le s \le n)$，进行如下“游走”并定义余数轨迹：

• 从位置 $s$ 开始，依次取 $a_s,a_{s+1},\dots$，当走到 $n$ 后继续从 $1$ 开始，形成一个最多包含 $n$ 个元素的连续环段。
• 第 $t$ 步的余数轨迹值定义为

其中取模为标准余数，落在区间 $[0,M-1]$。

要求轨迹互异：在允许的最大步数 $L_s$ 内，$S_1,S_2,\dots,S_{L_s}$ 两两不同；若再取一步会导致出现已出现过的余数值，则停止；若已取满 $n$ 步也停止。轨迹只包含 $t \ge 1$ 的 $S_t$，不包含初始 $0$。

定义起点 $s$ 的游走长度 $L_s$ 为以上规则下可达到的最大步数。请计算所有起点的游走长度之和 $\displaystyle \sum_{s=1}^{n} L_s$。

输入描述

每个测试文件包含多组测试数据。第一行输入一个整数 $T(1 \le T \le 10^5)$ 表示测试组数，每组测试数据描述如下：

• 第一行输入两个整数 $n,M \;(1 \le n \le 2 \times 10^5,\;1 \le M \le 2 \times 10^5)$。
• 第二行输入 $n$ 个整数 $a_1,a_2,\dots,a_n \;(-10^9 \le a_i \le 10^9)$。

保证所有测试数据的 $n$ 之和不超过 $2 \times 10^5$。

输出描述

对于每组测试数据，输出一行一个整数，表示该组数据的 $\displaystyle \sum_{s=1}^{n} L_s$。

样例1

输入

2
5 3
1 2 2 1 2
4 5
5 0 5 0

输出

11
4