Задачи
НВП
НВП
Мистер C интересуется задачей поиска Наибольшей Возрастающей Подпоследовательности. Пусть задана последовательность \textbf{S} = \textbf{s_1, s_2, …, s_n}. Наибольшей Возрастающей Подпоследовательностью является такая подпоследовательность \textbf{L} = \textbf{l_1, l_2, …, l_k} из \textbf{S}, что \textbf{l_1} < \textbf{l_2} < … < \textbf{l_k}.
По заданной последовательности \textbf{S }следует найти суммарную длину \textbf{НВП} каждой подпоследовательности \textbf{S} ненулевой длины, в которой элементы стоят рядом!
\InputFile
Первая строка содержит количество тестов \textbf{t}. Далее следуют \textbf{t} самих тестов.
Первая строка каждого теста содержит длину \textbf{n }(\textbf{1 }≤ \textbf{n }≤ \textbf{500}) последовательности \textbf{S}. Каждая из следующих \textbf{n }строк содержит целое \textbf{s_i} (\textbf{1 }≤ \textbf{s_i} ≤ \textbf{n}) - \textbf{i}-ый элемент \textbf{S}. Все элементы \textbf{S }различны.
\OutputFile
Вывести \textbf{t} строк, по одной строке для каждого теста.
Каждая строка имеет формат "\textbf{Case #i: S}", где \textbf{i} - номер теста, \textbf{S }- общая длина \textbf{LIS} всех последовательных подпоследовательностей \textbf{S}.
Входные данные #1
1 3 3 1 2
Выходные данные #1
Case #1: 8