DA-F93-CA1-1

Time Limit: 2 Seconds    Memory Limit: 32768 KB

اتاق ملاقات

تعداد زیادی هنرمند برای نمایش آثار خود قرار ملاقات می گذارند. اتاق ملاقات جایی است که در آن قرار ملاقات می گذارند!!! اتاق ملاقات در هر روز 10 ساعت قابل استفاده است. دو قرار ملاقات را نمی توان به طور همزمان در اتاق ملاقات برگزار کرد. بنابرین از میان تمام قرار ملاقات هایی که قرار است در یک روز صورت بگیرند تنها تعدادی از آنها که با هم تداخل ندارند را میتوان برگزار کرد. برنامه ای بنویسید که حداکثر تعداد قرار ملاقات هایی را که درهر روز می توان برگزار کرد مشخص کند. فرض کنید که اتاق ملاقات از ساعت 0 تا 10 ( 10 ساعت) قابل استفاده است. زمان شروع و پایان هر قرار ملاقات به شما داده شده می شود. زمان شروع و پایان اعداد صحیح اند و هر قرار ملاقات حداقل یک ساعت طول می کشد. در هر روز حداکثر 20 قرار ملاقات قرار است صورت بگیرد.

 

Input

در خط اول تعداد روزها (1<=n<=100) داده میشود. سپس به ازای هر روز,  ساعت شروع و پایان قرار ملاقات هایی که قرار است در آن روز صورت بگیرد داده میشود. به ازای هر قرارملاقات دو عدد صحیح داده میشود: زمان شروع 0<=s<=9 و زمان پایان 1<=f<=10 و داریم s<f. در هر روز آخرین خط  ورودی شامل 0 0 است که بیانگر پایان یافتن قرار ملاقات های آن روز می باشد.

 

 

 

Output

خروجی شامل n خط است. در خط  i ام حداکثر تعداد قرار ملاقات هایی را که می توان در روز i ام برگزار کرد چاپ کنید.

 

 

Sample Input

3

0 6

5 7

8 9

5 9

1 2

3 4

0 5

0 0

6 10

5 6

0 3

0 5

3 5

4 5

0 0

1 5

3 9

0 0

Sample Output

4

4

1

Submit