Диаманты
Общая стоимость бриллианта определяется его массой в каратах, а также чистотой. Большой алмаз со многими недостатками может стоить меньше меньшего алмаза но безупречного. Чистота алмаза описывается по шкале 0.0 - 10.0, принятой Американским обществом драгоценных камней, где 0.0 представляет собой безупречный алмаз, а 10.0 представляет собой несовершенный алмаз.
Задана последовательность из n диамантов, каждый весом w[i] в каратах и чистотой c[i] по выше указанной шкале. Найдите самую длинную подпоследовательность бриллиантов, для которой вес и прозрачность являются более выгодными для покупателя.
В следующей последовательности бриллиантов
самой длинной желательной подпоследовательностью является
потому что веса строго возрастают, а прозрачности строго уменьшаются.
Входные данные
Первая строка содержит количество тестов t (1 ≤ t ≤ 100). Каждый тест начинается строкой, содержащей количество диамант n (1 ≤ n ≤ 200). Каждая из следующих n строк содержит 2 действительных числа w[i] и c[i], (0.0 ≤ w[i], c[i] ≤ 10.0) - вес в каратах и прозрачность i-го диаманта.
Выходные данные
Для каждого теста выведите в отдельной строке длину самой длинной желанной подпоследовательности бриллиантов.