Розташування Конференц-Залу#6948

Розташування Конференц-Залу

1 секунда

128 мегабайтів

Легка

Факультет інженерії ПНУ має велику залу для засідань, де співробітники факультету можуть організовувати заходи та зустрічі. Використання зали для засідань має бути зарезервоване заздалегідь. Оскільки зала для засідань доступна $10$ годин на день і може бути кілька заходів, які хочуть скористатися залою, найкраща політика використання полягає в максимізації кількості заходів за день.

Припустимо, що зала для засідань доступна з часу $0$ до $10$ ( $10$ годин). Маючи список часу початку та закінчення кожного кандидатського заходу, ви повинні написати програму, яка вибере заходи, що вписуються в залу для засідань (тобто їхні часи не перетинаються) і забезпечить максимальну кількість заходів за день.

Вхідні дані

Перший рядок — це додатне ціле число $n$ ( $1 \leq n \leq 100$ 1 \leq n \leq 100), яке визначає кількість днів (тестових випадків). Кожен тестовий випадок складається з часу кандидатських заходів (менше ніж $20$ заходів). Час кожного заходу включає $2$ цілі числа, які є часом початку ( $s$ ) та часом закінчення ( $f$ ), $0 \leq s \leq 9$ 0 \leq s \leq 9, $1 \leq f \leq 10$ 1 \leq f \leq 10 та $s < f$ s < f.

Рядок, що містить $00$ , вказує на кінець кожного тестового випадку. Зверніть увагу, що захід має тривати принаймні $1$ годину.

Вихідні дані

Для кожного тестового випадку виведіть максимальну кількість заходів, які можна організувати в залі для засідань.

Приклади

Приклад 1