Serial Number

The guitarist Kangto is about to perform. Right before he goes on stage, his guitar gets mixed up with everyone else's guitars, and he has forgotten which one is his.

Luckily, every guitar carries a distinct (unique) serial number. Kangto only remembers one thing: if he adds up the serial numbers of all the guitars that were originally his, the total is a multiple of $M$.

Given the serial numbers of all the guitars on stage and the integer $M$, find the largest possible number of guitars that could be Kangto's. In other words, when you choose a set of guitars whose serial numbers sum to a multiple of $M$, print the maximum number of guitars you can choose.

The first line contains the number of test cases. Each test case is given in the following format.

• First line: the number of guitars $N$ and the integer $M$. ($1 \le N \le 500$, $1 \le M \le 100{,}000$)
• Second line: the serial numbers $S_1, S_2, \dots, S_N$. ($0 \le S_i \le 100{,}000$; all serial numbers are distinct.)

For each test case, print on its own line the maximum number of guitars you can choose so that the sum of their serial numbers is a multiple of $M$.

Only inputs for which an answer exists are given.