Діаманти#8174
Загальна вартість діаманта визначається його масою в каратах та чистотою. Великий діамант з багатьма недоліками може коштувати менше, ніж менший, але бездоганний діамант. Чистота діаманта оцінюється за шкалою від до , прийнятою Американським товариством дорогоцінних каменів, де означає бездоганний діамант, а — недосконалий.
Дано послідовність з діамантів, кожен з яких має вагу w_i в каратах і чистоту c_i за вищезазначеною шкалою. Потрібно знайти найдовшу підпослідовність діамантів, для якої вага і прозорість є більш вигідними для покупця.
У наведеній послідовності діамантів
найдовшою бажаною підпослідовністю є
оскільки ваги строго зростають, а прозорості строго зменшуються.
Перший рядок містить кількість тестів (1 \le t \le 100). Кожен тест починається з рядка, що містить кількість діамантів (1 \le n \le 200). Кожен з наступних рядків містить дійсних числа w_i і c_i, (0.0 \le w_i, c_i \le 10.0) — вага в каратах і прозорість -го діаманта.
Для кожного тесту виведіть в окремому рядку довжину найдовшої бажаної підпослідовності діамантів.
Приклад 1