곱셈 삼중항

면접 대비

시간 제한40초메모리 제한1024 MB

요약

한 값이 나머지 두 값의 곱이 되는 인덱스 삼중쌍의 개수를 센다. 0과 중복 값을 처리해야 한다.

문제

N개의 정수 A1, A2, ..., A****N이 주어진다. 다음 조건 중 적어도 하나를 만족하는 삼중항 (x, y, z) (1 ≤ x < y < z ≤ N)의 개수를 세라.

첫 줄에 테스트 케이스의 수 T가 주어진다. T개의 테스트 케이스가 이어진다. 각 테스트 케이스의 첫 줄에는 정수 N이 주어지며, 이는 배열 A의 정수 개수이다. 둘째 줄에는 N개의 정수 Ai가 주어지며, i번째 값은 i번째 정수의 값이다.

각 테스트 케이스마다 Case #x: y 형식의 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호(1부터 시작)이고, y는 문제의 조건을 만족하는 삼중항의 개수이다.

예제 1에서 문제의 조건을 만족하는 유일한 삼중항은 (2, 4, 5)이다. 두 번째, 네 번째, 다섯 번째 정수가 각각 2, 6, 3이고 2 × 3 = 6이므로 이 삼중항은 유효하다.

예제 2에서 문제의 조건을 만족하는 여섯 개의 삼중항은 (1, 2, 3), (1, 3, 4), (1, 4, 5), (1, 5, 6), (2, 3, 5), (2, 4, 6)이다.

예제 3에서는 삼중항 (1, 2, 3)을 한 번만 세도록 하라.

예제 4에서는 배열의 어떤 두 정수의 곱도 배열에 없으므로 문제의 조건을 만족하는 삼중항이 없다.

예제 1

입력

4
6
5 2 4 6 3 1
6
2 4 8 16 32 64
3
1 1 1
3
200000 200000 200000

예상 출력

Case #1: 1
Case #2: 6
Case #3: 1
Case #4: 0