시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 139 35 26 23.214%

문제

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

평일에 열리는 파티는 저녁에만 두세개가 열리지만 토요일에는 하루종일 많은 파티들이 열린다. 어떤 파티는 아침 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+XHVjNWVjXHViN2VjXHVhYzFjXHVjNzU4IFx1ZDE0Y1x1YzJhNFx1ZDJiOFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQgXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBcdWNjYWJcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzgxNVx1YzIxOCBwXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4mbmJzcDsocCZsZTsxMDApIFx1Yzc3NCBwXHViMjk0IFx1ZDMwY1x1ZDJmMFx1Yzc1OCBcdWFkZjggXHViMGEwXHVjNWQwIFx1YzVmNFx1YjlhY1x1YjI5NCBcdWQzMGNcdWQyZjBcdWM3NTggXHVjMjE4XHVjNzc0XHViMmU0LiBwXHVhYzAwIDBcdWM3NzRcdWJhNzQgXHVjNzg1XHViODI1XHVjNzU4IFx1YjA1ZFx1Yzc0NCBcdWM3NThcdWJiZjhcdWQ1NWNcdWIyZTQuIFx1Yzc3NFx1YzViNFx1YzljMFx1YjI5NCBwXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMFx1YjI5NCBzIFx1YzY0MCBlXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDggJmxlOyBzICZsdDsgZSAmbGU7IDI0KSBzXHViMjk0IFx1ZDMwY1x1ZDJmMFx1Yzc1OCBcdWMyZGNcdWM3OTFcdWMyZGNcdWFjMDRcdWM3NDQgXHVjNzU4XHViYmY4XHVkNTU4XHVhY2UwIGVcdWIyOTQgXHVkMzBjXHVkMmYwXHVhYzAwIFx1YjA1ZFx1YjA5OFx1YjI5NCBcdWMyZGNcdWFjMDRcdWM3NDQgXHVjNzU4XHViYmY4XHVkNTVjXHViMmU0LiBcdWMyZGNcdWM3OTFcdWMyZGNcdWFjMDRcdWFjZmMgXHViMDVkXHVjMmRjXHVhYzA0XHVjNzc0IFx1YWMxOVx1Yzc0MCBcdWQzMGNcdWQyZjBcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM4IFx1YzIxOFx1YjNjNCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHViMmU0XHVjNzRjXHVjNzU4IFx1Y2Q5Y1x1YjgyNVx1ZDYxNVx1YzJkZFx1YzVkMCBcdWI5ZGVcdWNkOTRcdWM1YjQgXHVjZDljXHViODI1XHVkNTU4XHVjMmRjXHVjNjI0PFwvcD5cclxuXHJcbjxwcmU+XHJcbk9uIGRheSBkIEVtbWEgY2FuIGF0dGVuZCBhcyBtYW55IGFzIG4gcGFydGllcy48XC9wcmU+XHJcblxyXG48cD5uXHVjNzQwIFx1Y2Q1Y1x1YjMwMCBcdWFjMDggXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWQzMGNcdWQyZjBcdWM3NTggXHVjMjE4XHVjNzc0XHVhY2UwIGRcdWIyOTQgXHViYTg3XHViYzg4XHVjOWY4IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NzhcdWM5YzBcdWI5N2MgXHVhYzAwXHViOWFjXHVkMGE4XHViMmU0LiBcdWQxNGNcdWMyYTRcdWQyYjhcdWNmMDBcdWM3NzRcdWMyYTRcdWIyOTQgMVx1YmQ4MFx1ZDEzMCBcdWMyZGNcdWM3OTFcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiNDA1NSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlBhcnR5IFBhcnR5IFBhcnR5IiwiZGVzY3JpcHRpb24iOiI8cD5FbW1hIGhhcyBqdXN0IGdyYWR1YXRlZCBoaWdoIHNjaG9vbCBhbmQgaXQgaXMgdGhlIGN1c3RvbSBmb3IgdGhlIG5ldyBncmFkdWF0ZXMgdG8gdGhyb3cgcGFydGllcyBmb3IgdGhlbXNlbHZlcyBhbmQgaW52aXRlIGV2ZXJ5b25lIGluIHNjaG9vbCB0byBhdHRlbmQuIE5hdHVyYWxseSwgRW1tYSB3aXNoZXMgdG8gYXR0ZW5kIGFzIG1hbnkgcGFydGllcyBhcyBwb3NzaWJsZS4gVGhpcyBpcyBub3Qgc3VjaCBhIHByb2JsZW0gb24gYSB3ZWVrZGF5IHNpbmNlIHVzdWFsbHkgdGhlcmUgYXJlIG9ubHkgdHdvIG9yIHRocmVlIHBhcnRpZXMgaW4gdGhlIGV2ZW5pbmcuIEJ1dCwgU2F0dXJkYXlzIGFyZSBwYWNrZWQhIFR5cGljYWxseSBzb21lIHBhcnRpZXMgc3RhcnQgYXQgOCBBTSAoYnJlYWtmYXN0IGlzIHNlcnZlZCkgd2hpbGUgb3RoZXJzIG1pZ2h0IGVuZCBhdCBtaWRuaWdodCAobXVjaCB0byB0aGUgYW5ub3lhbmNlIG9mIHRoZSBuZWlnaGJvcnMpLiBFbW1hIG5hdHVyYWxseSB3YW50cyB0byBrbm93IGhvdyBtYW55IHBhcnRpZXMgc2hlIGNhbiBhdHRlbmQuPFwvcD5cclxuXHJcbjxwPkVhY2ggcGFydHkgaGFzIGEgc3RhcnRpbmcgYW5kIHN0b3BwaW5nIHRpbWUsIHdoaWNoIGFyZSBvbiB0aGUgaG91ci4gVGhlc2UgYXJlIGxpc3RlZCB2aWEgYSAyNC1ob3VyIGNsb2NrLiBGb3IgZXhhbXBsZSwgYSBwYXJ0eSBtaWdodCBzdGFydCBhdCAxMCBBTSAoMTApIGFuZCBlbmQgYXQgMiBQTSAoMTQpLiBUaGUgZWFybGllc3QgYSBwYXJ0eSBjYW4gc3RhcnQgaXMgOCBBTSAoOCkgYW5kIHRoZSBsYXRlc3QgaXQgY2FuIGVuZCBpcyBtaWRuaWdodCAoMjQpLiBJbiBvcmRlciBub3QgdG8gYmUgcnVkZSwgRW1tYSBzdGF5cyBhdCBlYWNoIHBhcnR5IGF0IGxlYXN0IG9uZSBoYWxmIGhvdXIgYW5kIHdpbGwgY29uc2lkZXIgdHJhdmVsaW5nIHRpbWUgYmV0d2VlbiBwYXJ0aWVzIHRvIGJlIGluc3RhbnRhbmVvdXMuIElmIHRoZXJlIGFyZSB0aW1lcyBkdXJpbmcgdGhlIGRheSB3aGVuIHRoZXJlIGFyZSBubyBwYXJ0aWVzIHRvIGF0dGVuZCwgc2hlJnJzcXVvO2xsIHNpbXBseSBnbyBob21lIGFuZCByZXN0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlcmUgd2lsbCBiZSBtdWx0aXBsZSB0ZXN0IGNhc2VzLiBFYWNoIHRlc3QgY2FzZSBzdGFydHMgd2l0aCBhIGxpbmUgY29udGFpbmluZyBhbiBpbnRlZ2VyIHAgKCZsZTsgMTAwKSBpbmRpY2F0aW5nIHRoZSBudW1iZXIgb2YgcGFydGllcyBvbiB0aGUgZ2l2ZW4gZGF5LiAoQSB2YWx1ZSBvZiBwID0gMCBpbmRpY2F0ZXMgZW5kIG9mIGlucHV0LikgVGhlIGZvbGxvd2luZyBwIGxpbmVzIGFyZSBlYWNoIG9mIHRoZSBmb3JtIHMgZSwgYm90aCBpbnRlZ2VycyB3aGVyZSA4ICZsZTsgcyAmbHQ7IGUgJmxlOyAyNCwgaW5kaWNhdGluZyBhIHBhcnR5IHRoYXQgc3RhcnRzIGF0IHRpbWUgcyBhbmQgZW5kcyBhdCB0aW1lIGUuIE5vdGUgdGhlcmUgbWF5IGJlIG11bHRpcGxlIHBhcnRpZXMgd2l0aCB0aGUgc2FtZSBzdGFydGluZyBhbmQgZW5kaW5nIHRpbWUuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggaW5wdXQgc2V0IG91dHB1dCBhIGxpbmUgb2YgdGhlIGZvcm08XC9wPlxyXG5cclxuPHByZT5PbiBkYXkgZCBFbW1hIGNhbiBhdHRlbmQgYXMgbWFueSBhcyBuIHBhcnRpZXMuPFwvcHJlPlxyXG5cclxuPHA+d2hlcmUgeW91IGRldGVybWluZSB0aGUgdmFsdWUgb2YgbiBhbmQgZCBpcyB0aGUgbnVtYmVyIG9mIHRoZSB0ZXN0IGNhc2Ugc3RhcnRpbmcgYXQgMS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=