모든 연속 부분수열의 LIS 길이 합

C 씨는 최장 증가 부분수열(LIS) 문제에 관심이 많다. 수열 $S = s_1, s_2, \ldots, s_N$이 주어진다. $S$의 부분수열 $L = l_1, l_2, \ldots, l_k$가 $l_1 < l_2 < \cdots < l_k$를 만족하면 증가 부분수열이고, 그중 가장 긴 것이 $S$의 LIS다.

연속 부분수열은 원래 수열에서 서로 인접한 원소만으로 이루어진 부분수열이다. 길이가 1 이상인 연속 부분수열마다 LIS의 길이를 구한 뒤, 그 길이를 모두 더한 값을 구하라.

첫 줄에 테스트 케이스의 개수 $T$가 주어진다. 그 뒤로 테스트 케이스가 $T$개 이어진다.

각 테스트 케이스의 첫 줄에는 수열 $S$의 길이 $N$ ($1 \le N \le 500$)이 주어진다.

이어지는 $N$개의 줄에는 정수 $s_i$ ($1 \le s_i \le N$)가 한 줄에 하나씩 주어진다. $s_i$는 $S$의 $i$번째 원소이고, $S$의 원소는 모두 서로 다르다.

테스트 케이스마다 한 줄씩, 입력과 같은 순서로 $T$줄을 출력한다.

$i$번째 줄의 형식은 Case #i: X다. $i$는 테스트 케이스 번호이고, $X$는 그 테스트 케이스에서 길이가 1 이상인 모든 연속 부분수열의 LIS 길이를 더한 값이다.