시리얼 넘버

기타리스트 강토는 공연을 앞두고 있다. 그런데 무대에 오르기 직전, 강토의 기타가 다른 사람들의 기타와 뒤섞였고, 강토는 어떤 기타가 자기 것인지 잊어버렸다.

다행히 모든 기타에는 서로 다른(유일한) 시리얼 넘버가 붙어 있다. 강토는 자신이 원래 가지고 있던 기타들의 시리얼 넘버를 모두 더하면 그 합이 $M$의 배수가 된다는 사실만 기억하고 있다.

무대 위에 놓인 모든 기타의 시리얼 넘버와 정수 $M$이 주어질 때, 강토의 기타가 될 수 있는 기타 개수의 최댓값을 구하여라. 즉, 시리얼 넘버의 합이 $M$의 배수가 되도록 기타들을 고를 때, 고를 수 있는 기타 개수의 최댓값을 출력하면 된다.

첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 다음과 같은 형식이다.

• 첫째 줄: 기타의 개수 $N$과 정수 $M$. ($1 \le N \le 500$, $1 \le M \le 100{,}000$)
• 둘째 줄: 기타의 시리얼 넘버 $S_1, S_2, \dots, S_N$. ($0 \le S_i \le 100{,}000$, 모든 시리얼 넘버는 서로 다르다.)

각 테스트 케이스마다, 시리얼 넘버의 합이 $M$의 배수가 되도록 기타를 골랐을 때 고를 수 있는 기타 개수의 최댓값을 한 줄에 하나씩 출력한다.

입력으로는 항상 답이 존재하는 경우만 주어진다.