시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 128 MB 68 21 16 33.333%

문제

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

다행히도, 모든 기타는 유니크한 시리얼 넘버를 가지고 있으며, 각 시리얼 넘버는 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+XHJcbiIsImhpbnQiOiI8aWZyYW1lIHdpZHRoPVwiNTYwXCIgaGVpZ2h0PVwiMzE1XCIgc3JjPVwiaHR0cHM6XC9cL3d3dy55b3V0dWJlLmNvbVwvZW1iZWRcL1pHMEtKWDVSYng0XCIgZnJhbWVib3JkZXI9XCIwXCIgYWxsb3c9XCJhY2NlbGVyb21ldGVyOyBhdXRvcGxheTsgZW5jcnlwdGVkLW1lZGlhOyBneXJvc2NvcGU7IHBpY3R1cmUtaW4tcGljdHVyZVwiIGFsbG93ZnVsbHNjcmVlbj48XC9pZnJhbWU+Iiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI1NDQ0IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiU2VyaWFsIE51bWJlcnMiLCJkZXNjcmlwdGlvbiI6IjxwPlRoZSBncmVhdCBndWl0YXIgcGxheWVyIEJlcm5oYXJkLUFudG9uIFBldGVyIENvYmFpbiBpcyBwbGF5aW5nIHdpdGggaGlzIGJhbmQgdGhlIEF3ZXNvbWUgQ3J5aW5nIE1ldGFsaGVhZHMgaW4gdGhlIHdvbmRlcmZ1bCBjaXR5IG9mIExlaWRlbi4gVGhlIHNob3cgZ29lcyB3ZWxsIGFuZCBCZXJuaGFyZC1BbnRvbiBpcyB2ZXJ5IGhhcHB5LCBidXQgYWZ0ZXIgdGhlIHNob3cgaGUgaGFzIGEgYmlnIHByb2JsZW06IGhpcyBndWl0YXJzIGFyZSBtaXhlZCB1cCB3aXRoIGFsbCB0aGUgZ3VpdGFycyBvZiB0aGUgb3RoZXIgZ3VpdGFyIHBsYXllcnMsIGFuZCBCZXJuaGFyZC1BbnRvbiBkb2VzIG5vdCByZW1lbWJlciB3aGljaCBndWl0YXJzIHdlcmUgaGlzLjxcL3A+XHJcblxyXG48cD5Gb3J0dW5hdGVseSwgZXZlcnkgZ3VpdGFyIGhhcyBhIHVuaXF1ZSBzZXJpYWwgbnVtYmVyIHdoaWNoIGlzIGFuIGludGVnZXIgYmV0d2VlbiAxIGFuZCAxMDAsIDAwMC4gVGhlIG9ubHkgdGhpbmcgdGhhdCBCZXJuaGFyZC1BbnRvbiByZW1lbWJlcnMgaXMgdGhhdCB0aGUgc3VtIG9mIGFsbCB0aGUgc2VyaWFsIG51bWJlcnMgb2YgaGlzIGd1aXRhcnMgaXMgYSBtdWx0aXBsZSBvZiBNLiBHaXZlbiBhbGwgc2VyaWFsIG51bWJlcnMgYW5kIHRoZSBudW1iZXIgTSwgY2FsY3VsYXRlIHRoZSBtYXhpbXVtIG51bWJlciBvZiBndWl0YXJzIHRoYXQgY291bGQgaGF2ZSBiZWVuIEJlcm5oYXJkLUFudG9uJnJzcXVvO3MuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiB0aGUgaW5wdXQgY29udGFpbnMgYSBzaW5nbGUgbnVtYmVyOiB0aGUgbnVtYmVyIG9mIHRlc3QgY2FzZXMgdG8gZm9sbG93LiBFYWNoIHRlc3QgY2FzZSBoYXMgdGhlIGZvbGxvd2luZyBmb3JtYXQ6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+T25lIGxpbmUgd2l0aCB0d28gaW50ZWdlcnMgTiBhbmQgTSwgc2F0aXNmeWluZyAxICZsZTsgTiAmbGU7IDUwMCBhbmQgMSAmbGU7IE0gJmxlOyAxMDAsIDAwMDogdGhlIHRvdGFsIG51bWJlciBvZiBndWl0YXJzIGFuZCB0aGUgbnVtYmVyIE0uPFwvbGk+XHJcblx0PGxpPk9uZSBsaW5lIHdpdGggTiBkaWZmZXJlbnQgaW50ZWdlcnMgUzxzdWI+MTxcL3N1Yj4gLi4uIFM8c3ViPk48XC9zdWI+IHNhdGlzZnlpbmcgMCAmbGU7IFM8c3ViPmk8XC9zdWI+ICZsZTsgMTAwLCAwMDA6IHRoZSBzZXJpYWwgbnVtYmVycyBvZiB0aGUgZ3VpdGFycy48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5JbnRlZ2VycyBvbiB0aGUgc2FtZSBsaW5lIGFyZSBzZXBhcmF0ZWQgYnkgc2luZ2xlIHNwYWNlcywgYW5kIHRoZXJlIHdpbGwgYWx3YXlzIGJlIGF0IGxlYXN0IG9uZSBzdWJzZXQgb2YgZ3VpdGFycyBzdWNoIHRoYXQgdGhlIHN1bSBvZiB0aGVpciBzZXJpYWwgbnVtYmVycyBpcyBhIG11bHRpcGxlIG9mIE0uPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGV2ZXJ5IHRlc3QgY2FzZSBpbiB0aGUgaW5wdXQsIHRoZSBvdXRwdXQgc2hvdWxkIGNvbnRhaW4gYSBzaW5nbGUgbnVtYmVyLCBvbiBhIHNpbmdsZSBsaW5lOiB0aGUgbWF4aW11bSBudW1iZXIgb2YgZ3VpdGFycyBzdWNoIHRoYXQgdGhlIHN1bSBvZiB0aGVpciBzZXJpYWwgbnVtYmVycyBpcyBhIG11bHRpcGxlIG9mIE0uPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d