시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 574 83 24 5.455%

문제

정인이는 Top Root호텔에서 예약을 관리하는 일을 하고 있다. 오늘 정인이는 호텔 예약을 관리하는 소프트웨어에서 버그를 발견했다. 이 버그로 인해서 방이 겹치게 예약되고 잘못 배정되는 일이 발생했다. 이 소프트웨어를 만든 회사는 이미 망해버렸다. 따라서, 정인이는 자신이 직접 버그를 고치고 대책을 세우기로 했다.

먼저, 정인이는 예약 정보를 모두 내보냈다. 이 정보에는 예약 코드와 입실 시간, 퇴실 시간이 적혀져 있다. 이 정보를 이용해서 방을 배정하려면 방이 적어도 몇 개나 필요한지 구하는 프로그램을 작성하시오. 방은 다시 사용하기 전에 반드시 청소되어야 한다. 정인이는 위험을 감수하지 않으려고 한다. 따라서, 방을 청소하는 시간은 항상 최대 청소 시간과 같다.

입력

입력은 여러 줄로 이루어져 있다. 첫째 줄에는 테스트 케이스의 개수 1 ≤ T ≤ 100가 주어진다. 각 테스트 케이스의 첫째 줄에는 예약의 수 1 ≤ B ≤ 5000와 한 방을 청소하는데 걸리는 시간 0 ≤ C ≤ 360가 주어진다. 청소 시간의 단위는 분이다.

다음 B개 줄에는 각 예약의 정보가 주어진다. 예약 정보는 예약 코드와 입실 시간, 퇴실 시간으로 이루어져 있다. 예약 코드는 알파벳과 숫자로만 이루어져 있으며, 최대 20글자이다. 날짜는 "YYYY-MM-DD HH:MM" 형식이고, 2013년부터 2016년 사이의 예약만 주어진다.

출력

각 테스트 케이스에 대해서, 필요한 방의 최소 개수를 출력한다. 윤년에 유의해서 문제를 풀어야 한다. 또, 일광 절약 시간제 (Daylight saving time)는 고려하지 않아도 된다. 

예제 입력 1

4
2 120
1 2013-07-01 15:59 2013-07-08 16:30
2 2013-07-08 17:30 2013-07-15 12:00
3 60
65 2013-07-08 14:30 2013-07-08 16:00
32 2013-07-01 16:00 2013-07-15 12:00
91 2013-07-01 16:00 2013-07-08 15:00
2 360
a7 2016-02-21 14:00 2016-02-28 21:00
xx 2016-03-01 01:00 2016-03-02 12:57
2 60
a9 2016-02-21 14:00 2016-02-28 11:00
a8 2016-02-28 12:00 2016-03-11 21:00

예제 출력 1

2
3
1
1
W3sicHJvYmxlbV9pZCI6IjkyMDMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQ2MzhcdWQxNTQgXHVjNjA4XHVjNTdkIiwiZGVzY3JpcHRpb24iOiI8cD5cdWM4MTVcdWM3NzhcdWM3NzRcdWIyOTQgVG9wIFJvb3RcdWQ2MzhcdWQxNTRcdWM1ZDBcdWMxMWMgXHVjNjA4XHVjNTdkXHVjNzQ0IFx1YWQwMFx1YjlhY1x1ZDU1OFx1YjI5NCBcdWM3N2NcdWM3NDQgXHVkNTU4XHVhY2UwIFx1Yzc4OFx1YjJlNC4gXHVjNjI0XHViMjk4IFx1YzgxNVx1Yzc3OFx1Yzc3NFx1YjI5NCBcdWQ2MzhcdWQxNTQgXHVjNjA4XHVjNTdkXHVjNzQ0IFx1YWQwMFx1YjlhY1x1ZDU1OFx1YjI5NCBcdWMxOGNcdWQ1MDRcdWQyYjhcdWM2ZThcdWM1YjRcdWM1ZDBcdWMxMWMgXHViYzg0XHVhZGY4XHViOTdjIFx1YmMxY1x1YWNhY1x1ZDU4OFx1YjJlNC4gXHVjNzc0IFx1YmM4NFx1YWRmOFx1Yjg1YyBcdWM3NzhcdWQ1NzRcdWMxMWMgXHViYzI5XHVjNzc0IFx1YWNiOVx1Y2U1OFx1YWM4YyBcdWM2MDhcdWM1N2RcdWI0MThcdWFjZTAgXHVjNzk4XHViYWJiIFx1YmMzMFx1YzgxNVx1YjQxOFx1YjI5NCBcdWM3N2NcdWM3NzQgXHViYzFjXHVjMGRkXHVkNTg4XHViMmU0LiBcdWM3NzQgXHVjMThjXHVkNTA0XHVkMmI4XHVjNmU4XHVjNWI0XHViOTdjIFx1YjljY1x1YjRlMCBcdWQ2OGNcdWMwYWNcdWIyOTQgXHVjNzc0XHViYmY4IFx1YjlkZFx1ZDU3NFx1YmM4NFx1YjgzOFx1YjJlNC4gXHViNTMwXHViNzdjXHVjMTFjLCBcdWM4MTVcdWM3NzhcdWM3NzRcdWIyOTQgXHVjNzkwXHVjMmUwXHVjNzc0IFx1YzljMVx1YzgxMSBcdWJjODRcdWFkZjhcdWI5N2MgXHVhY2UwXHVjZTU4XHVhY2UwIFx1YjMwMFx1Y2M0NVx1Yzc0NCBcdWMxMzhcdWM2YjBcdWFlMzBcdWI4NWMgXHVkNTg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWJhM2NcdWM4MDAsIFx1YzgxNVx1Yzc3OFx1Yzc3NFx1YjI5NCBcdWM2MDhcdWM1N2QgXHVjODE1XHViY2Y0XHViOTdjIFx1YmFhOFx1YjQ1MCBcdWIwYjRcdWJjZjRcdWIwYzhcdWIyZTQuIFx1Yzc3NCBcdWM4MTVcdWJjZjRcdWM1ZDBcdWIyOTQgXHVjNjA4XHVjNTdkIFx1Y2Y1NFx1YjRkY1x1YzY0MCBcdWM3ODVcdWMyZTQgXHVjMmRjXHVhYzA0LCBcdWQxZjRcdWMyZTQgXHVjMmRjXHVhYzA0XHVjNzc0IFx1YzgwMVx1ZDYwMFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1Yzc3NCBcdWM4MTVcdWJjZjRcdWI5N2MgXHVjNzc0XHVjNmE5XHVkNTc0XHVjMTFjIFx1YmMyOVx1Yzc0NCBcdWJjMzBcdWM4MTVcdWQ1NThcdWI4MjRcdWJhNzQgXHViYzI5XHVjNzc0IFx1YzgwMVx1YzViNFx1YjNjNCBcdWJhODcgXHVhYzFjXHViMDk4IFx1ZDU0NFx1YzY5NFx1ZDU1Y1x1YzljMCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC4gXHViYzI5XHVjNzQwIFx1YjJlNFx1YzJkYyBcdWMwYWNcdWM2YTlcdWQ1NThcdWFlMzAgXHVjODA0XHVjNWQwIFx1YmMxOFx1YjRkY1x1YzJkYyBcdWNjYWRcdWMxOGNcdWI0MThcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWM4MTVcdWM3NzhcdWM3NzRcdWIyOTQgXHVjNzA0XHVkNWQ4XHVjNzQ0IFx1YWMxMFx1YzIxOFx1ZDU1OFx1YzljMCBcdWM1NGFcdWM3M2NcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWI1MzBcdWI3N2NcdWMxMWMsIFx1YmMyOVx1Yzc0NCBcdWNjYWRcdWMxOGNcdWQ1NThcdWIyOTQgXHVjMmRjXHVhYzA0XHVjNzQwIFx1ZDU2ZFx1YzBjMSBcdWNkNWNcdWIzMDAgXHVjY2FkXHVjMThjIFx1YzJkY1x1YWMwNFx1YWNmYyBcdWFjMTlcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWM3ODVcdWI4MjVcdWM3NDAgXHVjNWVjXHViN2VjIFx1YzkwNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiBcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVhYzFjXHVjMjE4IDEgJmxlOyBUICZsZTsgMTAwXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWM2MDhcdWM1N2RcdWM3NTggXHVjMjE4IDEgJmxlOyBCICZsZTsgNTAwMFx1YzY0MCBcdWQ1NWMgXHViYzI5XHVjNzQ0IFx1Y2NhZFx1YzE4Y1x1ZDU1OFx1YjI5NFx1YjM3MCBcdWFjNzhcdWI5YWNcdWIyOTQgXHVjMmRjXHVhYzA0IDAgJmxlOyBDICZsZTsgMzYwXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjY2FkXHVjMThjIFx1YzJkY1x1YWMwNFx1Yzc1OCBcdWIyZThcdWM3MDRcdWIyOTQgXHViZDg0XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgQlx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhYzAxIFx1YzYwOFx1YzU3ZFx1Yzc1OCBcdWM4MTVcdWJjZjRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM2MDhcdWM1N2QgXHVjODE1XHViY2Y0XHViMjk0IFx1YzYwOFx1YzU3ZCBcdWNmNTRcdWI0ZGNcdWM2NDAgXHVjNzg1XHVjMmU0IFx1YzJkY1x1YWMwNCwgXHVkMWY0XHVjMmU0IFx1YzJkY1x1YWMwNFx1YzczY1x1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiBcdWM2MDhcdWM1N2QgXHVjZjU0XHViNGRjXHViMjk0IFx1YzU0Y1x1ZDMwY1x1YmNiM1x1YWNmYyBcdWMyMmJcdWM3OTBcdWI4NWNcdWI5Y2MgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YzczY1x1YmE3MCwgXHVjZDVjXHViMzAwIDIwXHVhZTAwXHVjNzkwXHVjNzc0XHViMmU0LiBcdWIwYTBcdWM5ZGNcdWIyOTQgJnF1b3Q7WVlZWS1NTS1ERCBISDpNTSZxdW90OyBcdWQ2MTVcdWMyZGRcdWM3NzRcdWFjZTAsIDIwMTNcdWIxNDRcdWJkODBcdWQxMzAgMjAxNlx1YjE0NCBcdWMwYWNcdWM3NzRcdWM3NTggXHVjNjA4XHVjNTdkXHViOWNjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMsIFx1ZDU0NFx1YzY5NFx1ZDU1YyBcdWJjMjlcdWM3NTggXHVjZDVjXHVjMThjIFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YzcyNFx1YjE0NFx1YzVkMCBcdWM3MjBcdWM3NThcdWQ1NzRcdWMxMWMgXHViYjM4XHVjODFjXHViOTdjIFx1ZDQ4MFx1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1YjYxMCwgXHVjNzdjXHVhZDExIFx1YzgwOFx1YzU3ZCBcdWMyZGNcdWFjMDRcdWM4MWMgKERheWxpZ2h0IHNhdmluZyB0aW1lKVx1YjI5NCBcdWFjZTBcdWI4MjRcdWQ1NThcdWM5YzAgXHVjNTRhXHVjNTQ0XHViM2M0IFx1YjQxY1x1YjJlNC4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI5MjAzIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQm9va2luZyIsImRlc2NyaXB0aW9uIjoiPHA+UGllcnJlIGlzIGluIGdyZWF0IHRyb3VibGUgdG9kYXkhIEhlIGlzIHJlc3BvbnNpYmxlIGZvciBtYW5hZ2luZyB0aGUgYm9va2luZ3MgZm9yIHRoZSBBQ00gKEFjY29tb2RhdGlvbiB3aXRoIE1vZGVyYXRlIENvc3RzKSBob3RlbCBhbmQgaGFzIGp1c3QgcmVhbGl6ZWQgdGhhdCB0aGUgYm9va2luZyBzb2Z0d2FyZSBoYXMgYSBzZXZlcmUgYnVnLiBJdCBoYXMgY3JlYXRlZCBvdmVybGFwcGluZyBhbmQgd3Jvbmcgcm9vbSBhc3NpZ25tZW50cy4gUGllcnJlIGlzIG5vdyB3b3JyaWVkIHRoYXQgdGhlIGhvdGVsIG1pZ2h0IGJlIG92ZXJib29rZWQuIFNpbmNlIHRoZSBzb2Z0d2FyZSBtYW51ZmFjdHVyZXIgaXMgbmVpdGhlciB2ZXJ5IHJlc3BvbnNpdmUgbm9yIGNvbXBldGVudCwgaGUgbXVzdCBjaGVjayB0aGlzIGhpbXNlbGYsIHNvIHRoYXQgaGUgY2FuIHRpbWVseSB0YWtlIGNvdW50ZXJtZWFzdXJlcyBpZiBuZWNlc3NhcnkuPFwvcD5cclxuXHJcbjxwPkZvcnR1bmF0ZWx5LCBQaWVycmUgd2FzIGFibGUgdG8gZXhwb3J0IGFsbCBvcmlnaW5hbCBib29raW5ncyAoaW5jbHVkaW5nIHJlc2VydmF0aW9uIGNvZGVzIHBsdXMgY29ycmVjdCBhbmQgdmFsaWQgZGF0ZXMgb2YgYXJyaXZhbCBhbmQgZGVwYXJ0dXJlKS4gVGhlIG9ubHkgaW5mb3JtYXRpb24gdGhhdCBnb3QgbG9zdCBpcyB0aGUgdGltZSBvZiB0aGUgYm9va2luZyBwbGFjZW1lbnRzLCBzbyB0aGF0IFBpZXJyZSBjYW5ub3QgcmV0cmlldmUgYW55IGJvb2tpbmcgcHJpb3JpdGllcyAoZS5nLiwgZmlyc3QtY29tZS1maXJzdC1zZXJ2ZSkuIFVzaW5nIHRoZSBhdmFpbGFibGUgaW5mb3JtYXRpb24sIGNvdWxkIHlvdSBwbGVhc2UgaGVscCBQaWVycmUgb3V0IGFuZCB0ZWxsIGhpbSBhIHJvb20gYXNzaWdubWVudCB3aXRoIHRoZSBtaW5pbXVtIG51bWJlciBvZiByb29tcyB0aGF0IHNhdGlzXHVmYjAxZXMgYWxsIGJvb2tpbmdzPyBQbGVhc2UgYmUgYXdhcmUgdGhhdCBhIHJvb20gbXVzdCBhbHdheXMgYmUgY2xlYW5lZCBiZWZvcmUgcmV1c2UuIFNpbmNlIFBpZXJyZSBkb2VzIG5vdCB3YW50IHRvIHRha2UgYW55IHJpc2tzLCBoZSB0ZWxscyB5b3UgdG8gb25seSBjb25zaWRlciB0aGUgbWF4aW11bSBjbGVhbmluZyB0aW1lLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGlucHV0IGNvbnNpc3RzIG9mIHNldmVyYWwgbGluZXMuIFRoZSBcdWZiMDFyc3QgbGluZSBjb250YWlucyAxICZsZTsgVCAmbGU7IDEwMCwgdGhlIG51bWJlciBvZiB0ZXN0IGNhc2VzLiBFYWNoIHRlc3QgY2FzZSBzdGFydHMgd2l0aCBhIGxpbmUgY29udGFpbmluZyB0d28gaW50ZWdlcnMgMSAmbGU7IEIgJmxlOyA1IDAwMCwgdGhlIG51bWJlciBvZiBib29raW5ncywgYW5kIDAgJmxlOyBDICZsZTsgMzYwLCB0aGUgY2xlYW5pbmcgdGltZSAoaW4gbWludXRlcykgZm9yIG9uZSByb29tLiBUaGVuIGZvbGxvdyBCIGxpbmVzLCBlYWNoIGNvbnRhaW5pbmcgdGhlIHJlc2VydmF0aW9uIGNvZGUgKGEgcmFuZG9tIGFscGhhbnVtZXJpYyBzdHJpbmcgb2YgdXAgMjAgY2hhcmFjdGVycykgYW5kIHRoZSBkYXRlcyBvZiBhcnJpdmFsIGFuZCBkZXBhcnR1cmUgb2Ygb25lIGJvb2tpbmcuIERhdGVzIGFyZSBnaXZlbiBhcyBzdHJpbmdzIGluIHRoZSBmb3JtYXQgJnF1b3Q7WVlZWS1NTS1ERCBISDpNTSZxdW90OyAoc2VlIGV4YW1wbGUgdGVzdCBjYXNlKSwgd2hlcmUgcmVzZXJ2YXRpb25zIGFyZSBvbmx5IGZvciB0aGUgeWVhcnMgMjAxMyB1bnRpbCAyMDE2LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHRlc3QgY2FzZSwgcHJpbnQgdGhlIG1pbmltdW0gbnVtYmVyIG9mIG5lZWRlZCByb29tcyBvbiBhIHNpbmdsZSBsaW5lIHdpdGhvdXQgYW55IGFkZGl0aW9uYWwgYmxhbmtzLiBCZSBhd2FyZSBvZiBsZWFwIHllYXJzIGJ1dCBpZ25vcmUgZGF5bGlnaHQgc2F2aW5nIHRpbWUuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d