시리얼 넘버

위대한 기타리스트 강토는 공연을 앞두고 있다. 이제 무대에 올라가야 하는데, 기타가 다른 사람들의 기타와 섞이고 말았다. 또, 강토는 어떤 기타가 자기 것인지 까먹었다.

다행히도, 모든 기타는 유니크한 시리얼 넘버를 가지고 있으며, 각 시리얼 넘버는 1보다 크거나 같고, 100,000보다 작거나 같은 정수이다. 강토는 자신이 가지고 있는 기타의 시리얼 넘버를 모두 다 합하면 M의 배수가 된다는 것을 알 수 있다.

모든 기타의 시리얼 넘버와 M이 주어졌을 때, 가능한 강토의 기타 개수 중 최댓값을 구하는 프로그램을 작성하시오.

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

• 기타의 개수 N과 M이 주어진다. (1 ≤ N ≤ 500, 1 ≤ M ≤ 100,000)
• 기타의 시리얼 넘버 S1 ... SN이 주어진다. (0 ≤ Si ≤ 100,000)

각각의 테스트 케이스마다 시리얼 넘버의 합이 M의 배수가 되는 기타의 개수 중에서 최댓값을 출력한다.

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