Розташування Конференц-Залу
Факультет інженерії ПНУ має велику залу для засідань, де співробітники факультету можуть організовувати заходи та зустрічі. Використання зали для засідань має бути зарезервоване заздалегідь. Оскільки зала для засідань доступна 10 годин на день і може бути кілька заходів, які хочуть скористатися залою, найкраща політика використання полягає в максимізації кількості заходів за день.
Припустимо, що зала для засідань доступна з часу 0 до 10 (10 годин). Маючи список часу початку та закінчення кожного кандидатського заходу, ви повинні написати програму, яка вибере заходи, що вписуються в залу для засідань (тобто їхні часи не перетинаються) і забезпечить максимальну кількість заходів за день.
Вхідні дані
Перша строка — це додатне ціле число n (1 ≤ n ≤ 100), яке визначає кількість днів (тестових випадків). Кожен тестовий випадок складається з часу кандидатських заходів (менше ніж 20 заходів). Час кожного заходу включає 2 цілі числа, які є часом початку (s) та часом закінчення (f), 0 ≤ s ≤ 9, 1 ≤ f ≤ 10 та s < f.
Рядок, що містить 0 0, вказує на кінець кожного тестового випадку. Зверніть увагу, що захід має тривати принаймні 1 годину.
Вихідні дані
Для кожного тестового випадку виведіть максимальну кількість заходів, які можна організувати в залі для засідань.