Trapezoid Counting
시간 제한30초메모리 제한1024 MB
길이가 같은 막대도 서로 다른 것으로 세고 직사각형은 제외할 때, 주어진 막대 중 네 개를 골라 등변사다리꼴을 만드는 경우의 수를 센다.
문제
In this problem, we will consider a trapezoid to be a convex quadrilateral with exactly one pair of parallel sides. If the lengths of the two non-parallel sides are equal, we say the trapezoid is isosceles.
You have some wooden sticks of various lengths, and you need to pick exactly four of them to form the four sides of an isosceles trapezoid. How many different sets of four sticks will allow this? Even if two sticks have the same length, they are considered to be different sticks. Sticks could not be bended and broke into parts.
입력
The first line of the input gives the number of test cases, T. T test cases follow; each consists of two lines. The first line consists of one integer N, the number of sticks. The second line consists of N integers; the i-th of these, Li, represents the length of the i-th stick.
출력
For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1), and y is the number of different sets of four sticks that can form an isosceles trapezoid, as described above.
제한
- 1 ≤ T ≤ 100.
- 1 ≤ Li ≤ 109.
힌트
In Sample Case #1, there are five ways to choose four out of the five given sticks, and any one of those five sets of four sticks can be used to form an isosceles trapezoid.
In Sample Case #2, note that the set {1, 1, 3, 5} cannot form an isosceles trapezoid, even though two of its sticks are of equal length.
In Sample Case #3, note that the set {2, 2, 3, 3} can form a rectangle, but in this problem, a rectangle is not considered to be an isosceles trapezoid.