완전 부분배열

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

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

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 따른다. 각 테스트 케이스의 첫 줄에는 정수 N이 주어진다. 둘째 줄에는 Cristobal의 배열을 이루는 N개의 정수가 주어진다. i번째 정수는 Ai이다.

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

• 1 ≤ T ≤ 100.
• 모든 i에 대해 -100 ≤ Ai ≤ 100.

예제 1에는 합이 22인 [2 2] 하나의 완전 부분배열이 있다.

예제 2에는 세 개의 완전 부분배열이 있다:

• 합이 32인 [9].
• 합이 12인 [1].
• 합이 102인 [30 30 9 1 30].

예제 3에는 아홉 개의 완전 부분배열이 있다:

• 합이 22인 [4].
• 합이 22인 [4 0].
• 합이 22인 [4 0 0].
• 합이 02인 [0].
• 합이 02인 [0 0].
• 합이 42인 [0 0 16].
• 합이 02인 [0].
• 합이 42인 [0 16].
• 합이 42인 [16].

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