완전 부분 배열

Cristobal에게 N개의 (음수일 수도 있는) 정수로 이루어진 배열이 있다. 그의 배열에서 i번째 정수는 $A_{i}$이다. Cristobal의 배열에서 연속된 비어 있지 않은 부분 배열은 원소의 총합이 완전제곱수이면 완전하다. 완전제곱수는 음이 아닌 정수를 자기 자신과 곱한 수이다. 예를 들어, 처음 다섯 완전제곱수는 0, 1, 4, 9, 16이다.

완전한 부분 배열은 몇 개인가? 두 부분 배열에 같은 값들이 같은 순서로 들어 있더라도, 배열에서 시작 인덱스나 끝 인덱스가 다르면 서로 다른 부분 배열이다.

제한

메모리 제한: 1 GB. 1 ≤ T ≤ 100. -100 ≤ $A_{i}$ ≤ 100, 모든 i에 대해.

테스트 세트 1

시간 제한: 20초. 1 ≤ N ≤ 1000.

테스트 세트 2

시간 제한: 30초. 최대 5개의 케이스에 대해, 1 ≤ N ≤ $10^{5}$. 나머지 케이스에 대해, 1 ≤ N ≤ 1000.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스의 첫 줄에는 정수 N이 주어진다. 둘째 줄에는 Cristobal의 배열을 나타내는 N개의 정수가 주어진다. i번째 정수는 $A_{i}$이다.

각 테스트 케이스마다 Case #x: y을 포함하는 한 줄을 출력한다. 여기서 x은 테스트 케이스 번호이며(1부터 시작), y은 완전한 부분 배열의 개수이다.

예제 케이스 #1에는 완전한 부분 배열이 하나 있다. 그 부분 배열은 [2 2]이며 합은 $2^{2}$이다.

예제 케이스 #2에는 완전한 부분 배열이 세 개 있다.

• [9], 총합은 $3^{2}$이다.

• [1], 총합은 $1^{2}$이다.

• [30 30 9 1 30], 총합은 $10^{2}$이다.

예제 케이스 #3에는 완전한 부분 배열이 아홉 개 있다.

• [4], 총합은 $2^{2}$이다.

• [4 0], 총합은 $2^{2}$이다.

• [4 0 0], 총합은 $2^{2}$이다.

• [0], 총합은 $0^{2}$이다.

• [0 0], 총합은 $0^{2}$이다.

• [0 0 16], 총합은 $4^{2}$이다.

• [0], 총합은 $0^{2}$이다.

• [0 16], 총합은 $4^{2}$이다.

• [16], 총합은 $4^{2}$이다.

참고: 이 문제의 테스트 세트 2에는 인터프리터 방식이거나 느린 언어를 사용하는 것을 권장하지 않는다.