Each party has a starting and stopping time, which are on the hour. These are listed via a 24-hour clock. For example, a party might start at 10 AM (10) and end at 2 PM (14). The earliest a party can start is 8 AM (8) and the latest it can end is midnight (24). In order not to be rude, Emma stays at each party at least one half hour and will consider traveling time between parties to be instantaneous. If there are times during the day when there are no parties to attend, she will simply go home and rest.
There will be multiple test cases. Each test case starts with a line containing an integer p (<= 100) indicating the number of parties on the given day. (A value of p = 0 indicates end of input.) The following p lines are each of the form s e, both integers where 8 <= s < e <= 24, indicating a party that starts at time s and ends at time e. Note there may be multiple parties with the same starting and ending time.
For each input set output a line of the form
On day d Emma can attend as many as n parties.where you determine the value of n and d is the number of the test case starting at 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
On day 1 Emma can attend as many as 7 parties. On day 2 Emma can attend as many as 2 parties.
NOTE: problem D from 2008 East Central Regional Contest.