余配（rpai）

题目描述

Y 同学有一个长度为 $n$ 的非负整数序列 $a_1,a_2,\ldots,a_n$ 和一个正整数 $k$。他想从中选出两个不同的位置 $i,j$，满足 $1 \le i < j \le n$，并且 $a_i+a_j$ 能被 $k$ 整除。

现在给定多组数据，请你分别求出满足条件的下标对数量。

输入格式

第一行包含一个整数 $T$，表示测试组数。

对于每组测试数据，第一行包含两个整数 $n,k$。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

输出格式

对每组测试数据，输出一行一个整数，表示满足条件的下标对数量。

样例

样例输入 #1

2
5 4
1 3 2 6 5
5 3
1 2 3 4 5

样例输出 #1

3
4

数据范围与约定

对于 $100\%$ 的数据，保证 $1 \le T \le 2\times 10^5$，$1 \le \sum n \le 2\times 10^5$，$1 \le k \le 10^9$，$0 \le a_i \le 10^9$。

• 特殊性质 A：保证 $k=2$。
• 特殊性质 B：保证所有 $a_i<k$。