시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 128 MB3001129137.917%

문제

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

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

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

입력

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

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

출력

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

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

예제 입력 1

2
3 5
1 8 6
6 9
8 6 4 1 2 3

예제 출력 1

3
5

힌트

W3sicHJvYmxlbV9pZCI6IjU0NDQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMyZGNcdWI5YWNcdWM1YmMgXHViMTE4XHViYzg0IiwiZGVzY3JpcHRpb24iOiI8cD5cdWM3MDRcdWIzMDBcdWQ1NWMgXHVhZTMwXHVkMGMwXHViOWFjXHVjMmE0XHVkMmI4IFx1YWMxNVx1ZDFhMFx1YjI5NCBcdWFjZjVcdWM1ZjBcdWM3NDQgXHVjNTVlXHViNDUwXHVhY2UwIFx1Yzc4OFx1YjJlNC4gXHVjNzc0XHVjODFjIFx1YmIzNFx1YjMwMFx1YzVkMCBcdWM2MmNcdWI3N2NcdWFjMDBcdWM1N2MgXHVkNTU4XHViMjk0XHViMzcwLCBcdWFlMzBcdWQwYzBcdWFjMDAgXHViMmU0XHViOTc4IFx1YzBhY1x1Yjc4Y1x1YjRlNFx1Yzc1OCBcdWFlMzBcdWQwYzBcdWM2NDAgXHVjMTFlXHVjNzc0XHVhY2UwIFx1YjlkMFx1YzU1OFx1YjJlNC4gXHViNjEwLCBcdWFjMTVcdWQxYTBcdWIyOTQgXHVjNWI0XHViNWE0IFx1YWUzMFx1ZDBjMFx1YWMwMCBcdWM3OTBcdWFlMzAgXHVhYzgzXHVjNzc4XHVjOWMwIFx1YWU0Y1x1YmEzOVx1YzVjOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViMmU0XHVkNTg5XHVkNzg4XHViM2M0LCBcdWJhYThcdWI0ZTAgXHVhZTMwXHVkMGMwXHViMjk0IFx1YzcyMFx1YjJjOFx1ZDA2Y1x1ZDU1YyBcdWMyZGNcdWI5YWNcdWM1YmMgXHViMTE4XHViYzg0XHViOTdjIFx1YWMwMFx1YzljMFx1YWNlMCBcdWM3ODhcdWM3M2NcdWJhNzAsIFx1YWMwMSBcdWMyZGNcdWI5YWNcdWM1YmMgXHViMTE4XHViYzg0XHViMjk0IDFcdWJjZjRcdWIyZTQgXHVkMDZjXHVhYzcwXHViMDk4IFx1YWMxOVx1YWNlMCwgMTAwLDAwMFx1YmNmNFx1YjJlNCBcdWM3OTFcdWFjNzBcdWIwOTggXHVhYzE5XHVjNzQwIFx1YzgxNVx1YzIxOFx1Yzc3NFx1YjJlNC4gXHVhYzE1XHVkMWEwXHViMjk0IFx1Yzc5MFx1YzJlMFx1Yzc3NCBcdWFjMDBcdWM5YzBcdWFjZTAgXHVjNzg4XHViMjk0IFx1YWUzMFx1ZDBjMFx1Yzc1OCBcdWMyZGNcdWI5YWNcdWM1YmMgXHViMTE4XHViYzg0XHViOTdjIFx1YmFhOFx1YjQ1MCBcdWIyZTQgXHVkNTY5XHVkNTU4XHViYTc0IE1cdWM3NTggXHViYzMwXHVjMjE4XHVhYzAwIFx1YjQxY1x1YjJlNFx1YjI5NCBcdWFjODNcdWM3NDQgXHVjNTRjIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmFhOFx1YjRlMCBcdWFlMzBcdWQwYzBcdWM3NTggXHVjMmRjXHViOWFjXHVjNWJjIFx1YjExOFx1YmM4NFx1YzY0MCBNXHVjNzc0IFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YWMwMFx1YjJhNVx1ZDU1YyBcdWFjMTVcdWQxYTBcdWM3NTggXHVhZTMwXHVkMGMwIFx1YWMxY1x1YzIxOCBcdWM5MTEgXHVjZDVjXHViMzEzXHVhYzEyXHVjNzQ0IFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YWMxY1x1YzIxOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViMjk0IFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NDAgXHVkNjE1XHVjMmRkXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPlx1YWUzMFx1ZDBjMFx1Yzc1OCBcdWFjMWNcdWMyMTggTlx1YWNmYyBNXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBOICZsZTsgNTAwLCAxICZsZTsgTSAmbGU7IDEwMCwwMDApPFwvbGk+XHJcblx0PGxpPlx1YWUzMFx1ZDBjMFx1Yzc1OCBcdWMyZGNcdWI5YWNcdWM1YmMgXHViMTE4XHViYzg0IFM8c3ViPjE8XC9zdWI+IC4uLiBTPHN1Yj5OPFwvc3ViPlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgwICZsZTsgUzxzdWI+aTxcL3N1Yj4gJmxlOyAxMDAsMDAwKTxcL2xpPlxyXG48XC91bD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxXHVhYzAxXHVjNzU4IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI5YzhcdWIyZTQgXHVjMmRjXHViOWFjXHVjNWJjIFx1YjExOFx1YmM4NFx1Yzc1OCBcdWQ1NjlcdWM3NzQgTVx1Yzc1OCBcdWJjMzBcdWMyMThcdWFjMDAgXHViNDE4XHViMjk0IFx1YWUzMFx1ZDBjMFx1Yzc1OCBcdWFjMWNcdWMyMTggXHVjOTExXHVjNWQwXHVjMTFjIFx1Y2Q1Y1x1YjMxM1x1YWMxMlx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1ZDU2ZFx1YzBjMSBcdWIyZjVcdWM3NzQgXHVjODc0XHVjN2FjXHVkNTU4XHViMjk0IFx1YWNiZFx1YzZiMFx1YjljYyBcdWM3ODVcdWI4MjVcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiI8cD48aWZyYW1lIGFsbG93PVwiYWNjZWxlcm9tZXRlcjsgYXV0b3BsYXk7IGVuY3J5cHRlZC1tZWRpYTsgZ3lyb3Njb3BlOyBwaWN0dXJlLWluLXBpY3R1cmVcIiBhbGxvd2Z1bGxzY3JlZW49XCJcIiBmcmFtZWJvcmRlcj1cIjBcIiBoZWlnaHQ9XCIzMTVcIiBzcmM9XCJodHRwczpcL1wvd3d3LnlvdXR1YmUuY29tXC9lbWJlZFwvWkcwS0pYNVJieDRcIiB3aWR0aD1cIjU2MFwiPjxcL2lmcmFtZT48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjU0NDQiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJTZXJpYWwgTnVtYmVycyIsImRlc2NyaXB0aW9uIjoiPHA+VGhlIGdyZWF0IGd1aXRhciBwbGF5ZXIgQmVybmhhcmQtQW50b24gUGV0ZXIgQ29iYWluIGlzIHBsYXlpbmcgd2l0aCBoaXMgYmFuZCB0aGUgQXdlc29tZSBDcnlpbmcgTWV0YWxoZWFkcyBpbiB0aGUgd29uZGVyZnVsIGNpdHkgb2YgTGVpZGVuLiBUaGUgc2hvdyBnb2VzIHdlbGwgYW5kIEJlcm5oYXJkLUFudG9uIGlzIHZlcnkgaGFwcHksIGJ1dCBhZnRlciB0aGUgc2hvdyBoZSBoYXMgYSBiaWcgcHJvYmxlbTogaGlzIGd1aXRhcnMgYXJlIG1peGVkIHVwIHdpdGggYWxsIHRoZSBndWl0YXJzIG9mIHRoZSBvdGhlciBndWl0YXIgcGxheWVycywgYW5kIEJlcm5oYXJkLUFudG9uIGRvZXMgbm90IHJlbWVtYmVyIHdoaWNoIGd1aXRhcnMgd2VyZSBoaXMuPFwvcD5cclxuXHJcbjxwPkZvcnR1bmF0ZWx5LCBldmVyeSBndWl0YXIgaGFzIGEgdW5pcXVlIHNlcmlhbCBudW1iZXIgd2hpY2ggaXMgYW4gaW50ZWdlciBiZXR3ZWVuIDEgYW5kIDEwMCwgMDAwLiBUaGUgb25seSB0aGluZyB0aGF0IEJlcm5oYXJkLUFudG9uIHJlbWVtYmVycyBpcyB0aGF0IHRoZSBzdW0gb2YgYWxsIHRoZSBzZXJpYWwgbnVtYmVycyBvZiBoaXMgZ3VpdGFycyBpcyBhIG11bHRpcGxlIG9mIE0uIEdpdmVuIGFsbCBzZXJpYWwgbnVtYmVycyBhbmQgdGhlIG51bWJlciBNLCBjYWxjdWxhdGUgdGhlIG1heGltdW0gbnVtYmVyIG9mIGd1aXRhcnMgdGhhdCBjb3VsZCBoYXZlIGJlZW4gQmVybmhhcmQtQW50b24mcnNxdW87cy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIHRoZSBpbnB1dCBjb250YWlucyBhIHNpbmdsZSBudW1iZXI6IHRoZSBudW1iZXIgb2YgdGVzdCBjYXNlcyB0byBmb2xsb3cuIEVhY2ggdGVzdCBjYXNlIGhhcyB0aGUgZm9sbG93aW5nIGZvcm1hdDo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5PbmUgbGluZSB3aXRoIHR3byBpbnRlZ2VycyBOIGFuZCBNLCBzYXRpc2Z5aW5nIDEgJmxlOyBOICZsZTsgNTAwIGFuZCAxICZsZTsgTSAmbGU7IDEwMCwgMDAwOiB0aGUgdG90YWwgbnVtYmVyIG9mIGd1aXRhcnMgYW5kIHRoZSBudW1iZXIgTS48XC9saT5cclxuXHQ8bGk+T25lIGxpbmUgd2l0aCBOIGRpZmZlcmVudCBpbnRlZ2VycyBTPHN1Yj4xPFwvc3ViPiAuLi4gUzxzdWI+TjxcL3N1Yj4gc2F0aXNmeWluZyAwICZsZTsgUzxzdWI+aTxcL3N1Yj4gJmxlOyAxMDAsIDAwMDogdGhlIHNlcmlhbCBudW1iZXJzIG9mIHRoZSBndWl0YXJzLjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPkludGVnZXJzIG9uIHRoZSBzYW1lIGxpbmUgYXJlIHNlcGFyYXRlZCBieSBzaW5nbGUgc3BhY2VzLCBhbmQgdGhlcmUgd2lsbCBhbHdheXMgYmUgYXQgbGVhc3Qgb25lIHN1YnNldCBvZiBndWl0YXJzIHN1Y2ggdGhhdCB0aGUgc3VtIG9mIHRoZWlyIHNlcmlhbCBudW1iZXJzIGlzIGEgbXVsdGlwbGUgb2YgTS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZXZlcnkgdGVzdCBjYXNlIGluIHRoZSBpbnB1dCwgdGhlIG91dHB1dCBzaG91bGQgY29udGFpbiBhIHNpbmdsZSBudW1iZXIsIG9uIGEgc2luZ2xlIGxpbmU6IHRoZSBtYXhpbXVtIG51bWJlciBvZiBndWl0YXJzIHN1Y2ggdGhhdCB0aGUgc3VtIG9mIHRoZWlyIHNlcmlhbCBudW1iZXJzIGlzIGEgbXVsdGlwbGUgb2YgTS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d