Serial Number

Time limit3sMemory limit128 MB

Summary

Given distinct serial numbers and a modulus M, choose the largest subset whose sum is a multiple of M.

Level: Medium7 of 10
Topics: Dynamic programming, Number theory
Solved: No attempts yet

Problem

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.

Input

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.)

Output

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.

Examples1

Example 1
Input
```
2
3 5
1 8 6
6 9
8 6 4 1 2 3
```
Expected output
```
3
5
```