题目内容

在一个长度为 $n$ 的环形数据带上，按顺时针方向依次排列着整数 $a_1,a_2,\dots,a_n$，其中 $a_n$ 之后重新回到 $a_1$。给定一个正整数 $M$。

从某个起始位置 $s$ 开始连续读取数据，每次读取一个元素。设第 $t$ 次读取后累计读取到的数值总和为 $C_{s,t}$，定义该次读取对应的状态码为

其中取模结果为标准余数，范围为 $[0,M-1]$。

对于起始位置 $s$，若状态码序列 $Q_{s,1}, Q_{s,2}, \dots$ 中所有值两两不同，则继续读取；一旦下一个状态码与之前的某个状态码相同，或已经读取了 $n$ 个元素，则停止。将停止前读取的元素个数记为 $L_s$。注意，初始未读取任何元素时的状态 $0$ 不计入状态码序列。

请计算所有起始位置的长度之和 $\displaystyle \sum_{s=1}^{n} L_s$。

约束条件：测试组数不超过 10^5。每组中，$n$ 不超过 $2 \times 10^5$，$M$ 不超过 $2 \times 10^5$，每个 $a_i$ 的绝对值不超过 $10^9$。所有测试组的 $n$ 总和不超过 $2 \times 10^5$。

输入描述

第一行包含一个整数 T，表示测试数据组数。 每组测试数据占两行： 第一行包含两个整数 n 和 M，分别表示环形数据带的长度和模数。 第二行包含 n 个整数 a_1, a_2, \dots, a_n，依次表示环形数据带上的元素。 所有输入数值含义与题面约束一致。

输出描述

对于每组测试数据，输出一行一个整数，表示该组所有起始位置的最长读取长度之和。

样例1

输入

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

输出

11
4

说明

按题意模拟计算得到。