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