#6156. A * B Problem

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: igoodvegetablea

题目描述

这是一个非常简单的问题。

wmq 如今开始学习乘法了!他为了训练自己的乘法计算能力,写出了 n 个整数,并且对每两个数 a,b 都求出了它们的乘积 a\cdot b 。现在他想知道,在求出的 \frac{n(n-1)}{2} 个乘积中,除以给定的质数 m 余数为 k(0\leq k<m) 的有多少个。

输入格式

第一行为测试数据的组数。

对于每组测试数据,第一行为 2 个正整数 n,m(2\leq n,m\leq 60000) ,分别表示整数的个数以及除数。

接下来一行有 n 个整数,满足 0\leq a_{i}\leq 10^9

保证总输出行数 \sum{m}\leq 3\times 10^5

输出格式

对每组数据输出 m 行,其中第 i 行为除以 m 余数为 i-1 的数的个数。

样例

样例输入

2
4 5
2 0 1 7
4 2
2 0 1 6

样例输出

3
0
2
0
1
6
0

样例解释

样例求出的乘积分别为 0,0,0,2,7,14 ,因而除以 5 余数为 0 的有 3 个,余数为 1 的有 0 个,余数为 2 的有 2 个,余数为 3 的有 0 个,余数为 4 的有 1 个。