Server Time: Fri Dec 6, 2019 11:08 am
Welcome ( logout
1372 - Hexagonal Bamboo Fort
  PDF (English) Statistics Forum
Time Limit: 3 second(s) Memory Limit: 32 MB

You are given the lengths of N bamboo sticks that have distinct lengths. You have to select six sticks from those to make a fort of convex hexagonal shape. The hexagon should have a strictly positive area. For example, the sticks {1, 2, 3, 4, 5, 6} can be used to make a valid hexagon but the sticks {1, 2, 3, 4, 5, 20} can't make any valid hexagon with positive area.

How many ways you can do that? Consider that, two hexagons will be different, if the set of their sides are not same. For example, the hexagon with sides {1, 2, 3, 4, 5, 6} and {1, 3, 5, 4, 2, 6} are same but {1, 2, 3, 4, 5, 6} and {1, 2, 3, 4, 5, 7} are not.

Input

Input starts with an integer T (≤ 25), denoting the number of test cases.

Each case starts with a line containing an integer N (6 ≤ N ≤ 100). Next line contains N distinct integers giving the lengths of the sticks. Each of them will be between 1 and 105 (inclusive).

Output

For each case, print the case number and the number of ways six sticks can be selected to make a valid convex hexagon with positive area.

Sample Input

Output for Sample Input

3

6

1 2 3 4 5 6

8

1 2 5 20 30 10 100 400

8

179 259 263 265 506 146 222 828

Case 1: 1

Case 2: 1

Case 3: 28

 


Problem Setter: Tasnim Imran Sunny
Special Thanks: F.A. Rezaur Rahman Chowdhury, Pratyai Mazumder, Md. Nazmul Hasan, Jane Alam Jan
Developed and Maintained by
JANE ALAM JAN
Copyright © 2012
LightOJ, Jane Alam Jan