시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 142 36 27 23.478%

문제

아람이는 고등학교를 졸업하였다. 아람이네 마을에서는 학교의 모든 졸업생들이 참가할 수 있는 다양한 파티가 관습처럼 열리고 있다. 파티를 좋아하는 아람이는 최대한 많은 파티에 참가하려고 한다. 

평일에 열리는 파티는 저녁에만 두세개가 열리지만 토요일에는 하루종일 많은 파티들이 열린다. 어떤 파티는 아침 8시에 시작하여 자정(24시)에 끝나기도 한다. 아람이는 최대한 많은 파티에 참가하고 싶다.

각각의 파티는 시작시간과 끝시간이 정해져있다. 파티는 정각에 시작하여 정각에 끝난다. 예를 들어 10시에 파티가 시작한 파티가 오후2시(14시)에 끝날 수도 있고 가장 일찍 시작하는 파티는 아침 8시에 시작하고 이웃들의 항의가 있을 수 있기 때문에 아무리 늦게 끝나도 24시에는 끝나게 된다. 파티에 있을 때는 최소한 30분은 있어야 예의에 어긋나지 않는다. 아람이는 예의를 지키는 사람이다. 아람이는 축지법을 쓰기 때문에 파티간 이동시간은 신경쓰지 않아도 된다. 더 이상 참가할 파티가 없으면 아람이는 집에 돌아간다.

아람이가 갈 수 있는 최대 파티 수는 몇개인지 찾는 프로그램을 작성하시오.

입력

여러개의 테스트케이스가 주어진다 각 테스트케이스는 첫 번째 줄에 정수 p가 주어진다. (p≤100) 이 p는 파티의 그 날에 열리는 파티의 수이다. p가 0이면 입력의 끝을 의미한다. 이어지는 p개의 줄에는 s 와 e가 주어진다. (8 ≤ s < e ≤ 24) s는 파티의 시작시간을 의미하고 e는 파티가 끝나는 시간을 의미한다. 시작시간과 끝시간이 같은 파티가 주어질 수도 있다.

출력

다음의 출력형식에 맞추어 출력하시오

On day d Emma can attend as many as n parties.

n은 최대 갈 수 있는 파티의 수이고 d는 몇번째 테스트 케이스인지를 가리킨다. 테스트케이스는 1부터 시작한다.

예제 입력 1

8
12 13
13 14
12 13
9 10
9 10
12 13
12 14
9 11
3
14 15
14 15
14 15
0

예제 출력 1

On day 1 Emma can attend as many as 7 parties.
On day 2 Emma can attend as many as 2 parties.
W3sicHJvYmxlbV9pZCI6IjQwNTUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQzMGNcdWQyZjBcdWFjMDAgXHVjODhiXHVjNTQ0IFx1ZDMwY1x1ZDJmMFx1YWMwMCBcdWM4OGJcdWM1NDQiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzU0NFx1Yjc4Y1x1Yzc3NFx1YjI5NCBcdWFjZTBcdWI0ZjFcdWQ1NTlcdWFkNTBcdWI5N2MgXHVjODc4XHVjNWM1XHVkNTU4XHVjNjAwXHViMmU0LiBcdWM1NDRcdWI3OGNcdWM3NzRcdWIxMjQgXHViOWM4XHVjNzQ0XHVjNWQwXHVjMTFjXHViMjk0Jm5ic3A7XHVkNTU5XHVhZDUwXHVjNzU4IFx1YmFhOFx1YjRlMCBcdWM4NzhcdWM1YzVcdWMwZGRcdWI0ZTRcdWM3NzQgXHVjYzM4XHVhYzAwXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHViMmU0XHVjNTkxXHVkNTVjIFx1ZDMwY1x1ZDJmMFx1YWMwMCZuYnNwO1x1YWQwMFx1YzJiNVx1Y2M5OFx1YjdmYyBcdWM1ZjRcdWI5YWNcdWFjZTAgXHVjNzg4XHViMmU0LiBcdWQzMGNcdWQyZjBcdWI5N2MgXHVjODhiXHVjNTQ0XHVkNTU4XHViMjk0IFx1YzU0NFx1Yjc4Y1x1Yzc3NFx1YjI5NCZuYnNwO1x1Y2Q1Y1x1YjMwMFx1ZDU1YyBcdWI5Y2VcdWM3NDAgXHVkMzBjXHVkMmYwXHVjNWQwIFx1Y2MzOFx1YWMwMFx1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlx1ZDNjOVx1Yzc3Y1x1YzVkMCBcdWM1ZjRcdWI5YWNcdWIyOTQgXHVkMzBjXHVkMmYwXHViMjk0IFx1YzgwMFx1YjE0MVx1YzVkMFx1YjljYyZuYnNwO1x1YjQ1MFx1YzEzOFx1YWMxY1x1YWMwMCBcdWM1ZjRcdWI5YWNcdWM5YzBcdWI5Y2MmbmJzcDtcdWQxYTBcdWM2OTRcdWM3N2NcdWM1ZDBcdWIyOTQgXHVkNTU4XHViOGU4XHVjODg1XHVjNzdjIFx1YjljZVx1Yzc0MCBcdWQzMGNcdWQyZjBcdWI0ZTRcdWM3NzQgXHVjNWY0XHViOWIwXHViMmU0LiZuYnNwO1x1YzViNFx1YjVhNCBcdWQzMGNcdWQyZjBcdWIyOTQmbmJzcDtcdWM1NDRcdWNlNjggOFx1YzJkY1x1YzVkMCBcdWMyZGNcdWM3OTFcdWQ1NThcdWM1ZWMmbmJzcDtcdWM3OTBcdWM4MTUoMjRcdWMyZGMpXHVjNWQwIFx1YjA1ZFx1YjA5OFx1YWUzMFx1YjNjNCBcdWQ1NWNcdWIyZTQuIFx1YzU0NFx1Yjc4Y1x1Yzc3NFx1YjI5NCBcdWNkNWNcdWIzMDBcdWQ1NWMgXHViOWNlXHVjNzQwIFx1ZDMwY1x1ZDJmMFx1YzVkMCBcdWNjMzhcdWFjMDBcdWQ1NThcdWFjZTAgXHVjMmY2XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjMDFcdWFjMDFcdWM3NTggXHVkMzBjXHVkMmYwXHViMjk0IFx1YzJkY1x1Yzc5MVx1YzJkY1x1YWMwNFx1YWNmYyBcdWIwNWRcdWMyZGNcdWFjMDRcdWM3NzQgXHVjODE1XHVkNTc0XHVjODM4XHVjNzg4XHViMmU0LiBcdWQzMGNcdWQyZjBcdWIyOTQgXHVjODE1XHVhYzAxXHVjNWQwIFx1YzJkY1x1Yzc5MVx1ZDU1OFx1YzVlYyBcdWM4MTVcdWFjMDFcdWM1ZDAgXHViMDVkXHViMDljXHViMmU0LiBcdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0IDEwXHVjMmRjXHVjNWQwIFx1ZDMwY1x1ZDJmMFx1YWMwMCBcdWMyZGNcdWM3OTFcdWQ1NWMgXHVkMzBjXHVkMmYwXHVhYzAwIFx1YzYyNFx1ZDZjNDJcdWMyZGMoMTRcdWMyZGMpXHVjNWQwIFx1YjA1ZFx1YjBhMCBcdWMyMThcdWIzYzQgXHVjNzg4XHVhY2UwIFx1YWMwMFx1YzdhNSBcdWM3N2NcdWNjMGQgXHVjMmRjXHVjNzkxXHVkNTU4XHViMjk0IFx1ZDMwY1x1ZDJmMFx1YjI5NCBcdWM1NDRcdWNlNjggOFx1YzJkY1x1YzVkMCBcdWMyZGNcdWM3OTFcdWQ1NThcdWFjZTAgXHVjNzc0XHVjNmMzXHViNGU0XHVjNzU4IFx1ZDU2ZFx1Yzc1OFx1YWMwMCBcdWM3ODhcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAmbmJzcDtcdWM1NDRcdWJiMzRcdWI5YWMmbmJzcDtcdWIyYTZcdWFjOGMgXHViMDVkXHViMDk4XHViM2M0IDI0XHVjMmRjXHVjNWQwXHViMjk0Jm5ic3A7XHViMDVkXHViMDk4XHVhYzhjIFx1YjQxY1x1YjJlNC4gXHVkMzBjXHVkMmYwXHVjNWQwIFx1Yzc4OFx1Yzc0NCBcdWI1NGNcdWIyOTQgXHVjZDVjXHVjMThjXHVkNTVjIDMwXHViZDg0XHVjNzQwIFx1Yzc4OFx1YzViNFx1YzU3YyBcdWM2MDhcdWM3NThcdWM1ZDAgXHVjNWI0XHVhZTBiXHViMDk4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC4gXHVjNTQ0XHViNzhjXHVjNzc0XHViMjk0IFx1YzYwOFx1Yzc1OFx1Yjk3YyBcdWM5YzBcdWQwYTRcdWIyOTQgXHVjMGFjXHViNzhjXHVjNzc0XHViMmU0LiBcdWM1NDRcdWI3OGNcdWM3NzRcdWIyOTQgXHVjZDk1XHVjOWMwXHViYzk1XHVjNzQ0IFx1YzRmMFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAgXHVkMzBjXHVkMmYwXHVhYzA0IFx1Yzc3NFx1YjNkOVx1YzJkY1x1YWMwNFx1Yzc0MCBcdWMyZTBcdWFjYmRcdWM0ZjBcdWM5YzAgXHVjNTRhXHVjNTQ0XHViM2M0IFx1YjQxY1x1YjJlNC4gXHViMzU0IFx1Yzc3NFx1YzBjMSZuYnNwO1x1Y2MzOFx1YWMwMFx1ZDU2MCBcdWQzMGNcdWQyZjBcdWFjMDAgXHVjNWM2XHVjNzNjXHViYTc0IFx1YzU0NFx1Yjc4Y1x1Yzc3NFx1YjI5NCBcdWM5ZDFcdWM1ZDAgXHViM2NjXHVjNTQ0XHVhYzA0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM1NDRcdWI3OGNcdWM3NzRcdWFjMDAgXHVhYzA4IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjZDVjXHViMzAwIFx1ZDMwY1x1ZDJmMCBcdWMyMThcdWIyOTQgXHViYTg3XHVhYzFjXHVjNzc4XHVjOWMwIFx1Y2MzZVx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNWVjXHViN2VjXHVhYzFjXHVjNzU4IFx1ZDE0Y1x1YzJhNFx1ZDJiOFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQgXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBcdWNjYWIgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMCBcdWM4MTVcdWMyMTggcFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuJm5ic3A7KHAmbGU7MTAwKSBcdWM3NzQgcFx1YjI5NCBcdWQzMGNcdWQyZjBcdWM3NTggXHVhZGY4IFx1YjBhMFx1YzVkMCBcdWM1ZjRcdWI5YWNcdWIyOTQgXHVkMzBjXHVkMmYwXHVjNzU4IFx1YzIxOFx1Yzc3NFx1YjJlNC4gcFx1YWMwMCAwXHVjNzc0XHViYTc0IFx1Yzc4NVx1YjgyNVx1Yzc1OCBcdWIwNWRcdWM3NDQgXHVjNzU4XHViYmY4XHVkNTVjXHViMmU0LiBcdWM3NzRcdWM1YjRcdWM5YzBcdWIyOTQgcFx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDBcdWIyOTQgcyBcdWM2NDAgZVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICg4ICZsZTsgcyAmbHQ7IGUgJmxlOyAyNCkgc1x1YjI5NCBcdWQzMGNcdWQyZjBcdWM3NTggXHVjMmRjXHVjNzkxXHVjMmRjXHVhYzA0XHVjNzQ0IFx1Yzc1OFx1YmJmOFx1ZDU1OFx1YWNlMCBlXHViMjk0IFx1ZDMwY1x1ZDJmMFx1YWMwMCBcdWIwNWRcdWIwOThcdWIyOTQgXHVjMmRjXHVhYzA0XHVjNzQ0IFx1Yzc1OFx1YmJmOFx1ZDU1Y1x1YjJlNC4gXHVjMmRjXHVjNzkxXHVjMmRjXHVhYzA0XHVhY2ZjIFx1YjA1ZFx1YzJkY1x1YWMwNFx1Yzc3NCBcdWFjMTlcdWM3NDAgXHVkMzBjXHVkMmYwXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljOCBcdWMyMThcdWIzYzQgXHVjNzg4XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YjJlNFx1Yzc0Y1x1Yzc1OCBcdWNkOWNcdWI4MjVcdWQ2MTVcdWMyZGRcdWM1ZDAgXHViOWRlXHVjZDk0XHVjNWI0IFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YzJkY1x1YzYyNDxcL3A+XHJcblxyXG48cHJlPlxyXG5PbiBkYXkgZCBFbW1hIGNhbiBhdHRlbmQgYXMgbWFueSBhcyBuIHBhcnRpZXMuPFwvcHJlPlxyXG5cclxuPHA+blx1Yzc0MCBcdWNkNWNcdWIzMDAgXHVhYzA4IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVkMzBjXHVkMmYwXHVjNzU4IFx1YzIxOFx1Yzc3NFx1YWNlMCBkXHViMjk0IFx1YmE4N1x1YmM4OFx1YzlmOCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzc4XHVjOWMwXHViOTdjIFx1YWMwMFx1YjlhY1x1ZDBhOFx1YjJlNC4gXHVkMTRjXHVjMmE0XHVkMmI4XHVjZjAwXHVjNzc0XHVjMmE0XHViMjk0IDFcdWJkODBcdWQxMzAgXHVjMmRjXHVjNzkxXHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjQwNTUiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJQYXJ0eSBQYXJ0eSBQYXJ0eSIsImRlc2NyaXB0aW9uIjoiPHA+RW1tYSBoYXMganVzdCBncmFkdWF0ZWQgaGlnaCBzY2hvb2wgYW5kIGl0IGlzIHRoZSBjdXN0b20gZm9yIHRoZSBuZXcgZ3JhZHVhdGVzIHRvIHRocm93IHBhcnRpZXMgZm9yIHRoZW1zZWx2ZXMgYW5kIGludml0ZSBldmVyeW9uZSBpbiBzY2hvb2wgdG8gYXR0ZW5kLiBOYXR1cmFsbHksIEVtbWEgd2lzaGVzIHRvIGF0dGVuZCBhcyBtYW55IHBhcnRpZXMgYXMgcG9zc2libGUuIFRoaXMgaXMgbm90IHN1Y2ggYSBwcm9ibGVtIG9uIGEgd2Vla2RheSBzaW5jZSB1c3VhbGx5IHRoZXJlIGFyZSBvbmx5IHR3byBvciB0aHJlZSBwYXJ0aWVzIGluIHRoZSBldmVuaW5nLiBCdXQsIFNhdHVyZGF5cyBhcmUgcGFja2VkISBUeXBpY2FsbHkgc29tZSBwYXJ0aWVzIHN0YXJ0IGF0IDggQU0gKGJyZWFrZmFzdCBpcyBzZXJ2ZWQpIHdoaWxlIG90aGVycyBtaWdodCBlbmQgYXQgbWlkbmlnaHQgKG11Y2ggdG8gdGhlIGFubm95YW5jZSBvZiB0aGUgbmVpZ2hib3JzKS4gRW1tYSBuYXR1cmFsbHkgd2FudHMgdG8ga25vdyBob3cgbWFueSBwYXJ0aWVzIHNoZSBjYW4gYXR0ZW5kLjxcL3A+XHJcblxyXG48cD5FYWNoIHBhcnR5IGhhcyBhIHN0YXJ0aW5nIGFuZCBzdG9wcGluZyB0aW1lLCB3aGljaCBhcmUgb24gdGhlIGhvdXIuIFRoZXNlIGFyZSBsaXN0ZWQgdmlhIGEgMjQtaG91ciBjbG9jay4gRm9yIGV4YW1wbGUsIGEgcGFydHkgbWlnaHQgc3RhcnQgYXQgMTAgQU0gKDEwKSBhbmQgZW5kIGF0IDIgUE0gKDE0KS4gVGhlIGVhcmxpZXN0IGEgcGFydHkgY2FuIHN0YXJ0IGlzIDggQU0gKDgpIGFuZCB0aGUgbGF0ZXN0IGl0IGNhbiBlbmQgaXMgbWlkbmlnaHQgKDI0KS4gSW4gb3JkZXIgbm90IHRvIGJlIHJ1ZGUsIEVtbWEgc3RheXMgYXQgZWFjaCBwYXJ0eSBhdCBsZWFzdCBvbmUgaGFsZiBob3VyIGFuZCB3aWxsIGNvbnNpZGVyIHRyYXZlbGluZyB0aW1lIGJldHdlZW4gcGFydGllcyB0byBiZSBpbnN0YW50YW5lb3VzLiBJZiB0aGVyZSBhcmUgdGltZXMgZHVyaW5nIHRoZSBkYXkgd2hlbiB0aGVyZSBhcmUgbm8gcGFydGllcyB0byBhdHRlbmQsIHNoZSZyc3F1bztsbCBzaW1wbHkgZ28gaG9tZSBhbmQgcmVzdC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZXJlIHdpbGwgYmUgbXVsdGlwbGUgdGVzdCBjYXNlcy4gRWFjaCB0ZXN0IGNhc2Ugc3RhcnRzIHdpdGggYSBsaW5lIGNvbnRhaW5pbmcgYW4gaW50ZWdlciBwICgmbGU7IDEwMCkgaW5kaWNhdGluZyB0aGUgbnVtYmVyIG9mIHBhcnRpZXMgb24gdGhlIGdpdmVuIGRheS4gKEEgdmFsdWUgb2YgcCA9IDAgaW5kaWNhdGVzIGVuZCBvZiBpbnB1dC4pIFRoZSBmb2xsb3dpbmcgcCBsaW5lcyBhcmUgZWFjaCBvZiB0aGUgZm9ybSBzIGUsIGJvdGggaW50ZWdlcnMgd2hlcmUgOCAmbGU7IHMgJmx0OyBlICZsZTsgMjQsIGluZGljYXRpbmcgYSBwYXJ0eSB0aGF0IHN0YXJ0cyBhdCB0aW1lIHMgYW5kIGVuZHMgYXQgdGltZSBlLiBOb3RlIHRoZXJlIG1heSBiZSBtdWx0aXBsZSBwYXJ0aWVzIHdpdGggdGhlIHNhbWUgc3RhcnRpbmcgYW5kIGVuZGluZyB0aW1lLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIGlucHV0IHNldCBvdXRwdXQgYSBsaW5lIG9mIHRoZSBmb3JtPFwvcD5cclxuXHJcbjxwcmU+T24gZGF5IGQgRW1tYSBjYW4gYXR0ZW5kIGFzIG1hbnkgYXMgbiBwYXJ0aWVzLjxcL3ByZT5cclxuXHJcbjxwPndoZXJlIHlvdSBkZXRlcm1pbmUgdGhlIHZhbHVlIG9mIG4gYW5kIGQgaXMgdGhlIG51bWJlciBvZiB0aGUgdGVzdCBjYXNlIHN0YXJ0aW5nIGF0IDEuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d