{"raw_statement":[{"iden":"statement","content":"Tom has just found out that he can’t make a triangle using three line segments of lengths 1, 2 and 5. He has lots of different line segments and wants to know how many different triangles he can make. The triangles are different if the sets of their line segments’ lengths are different.\n\nThe first line contains the number of test cases _T_ (T ≤ 50). The first line of each test case contains the number of segments _N_ (N ≤ 100). The second line of each test case contains _N_ integers ai separated by spaces, ai is the length of _i_-th line segment (1 ≤ ai ≤ 105).\n\nFor each test case output one line containing “_Case #tc: num_”, where _tc_ is the number of the test case (starting from 1) and _num_ is the number of distinct triangles Tom can make.\n\n"},{"iden":"input","content":"The first line contains the number of test cases _T_ (T ≤ 50). The first line of each test case contains the number of segments _N_ (N ≤ 100). The second line of each test case contains _N_ integers ai separated by spaces, ai is the length of _i_-th line segment (1 ≤ ai ≤ 105)."},{"iden":"output","content":"For each test case output one line containing “_Case #tc: num_”, where _tc_ is the number of the test case (starting from 1) and _num_ is the number of distinct triangles Tom can make."},{"iden":"examples","content":"Input232 2 355 5 5 5 7OutputCase #1: 1Case #2: 2"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case $ k \\in \\{1, \\dots, T\\} $:  \n- Let $ N_k \\in \\mathbb{Z} $ denote the number of line segments.  \n- Let $ A_k = (a_{k,1}, a_{k,2}, \\dots, a_{k,N_k}) $ be a multiset of positive integers representing segment lengths.  \n\n**Constraints**  \n1. $ 1 \\le T \\le 50 $  \n2. For each $ k \\in \\{1, \\dots, T\\} $:  \n   - $ 1 \\le N_k \\le 100 $  \n   - $ 1 \\le a_{k,i} \\le 10^5 $ for all $ i \\in \\{1, \\dots, N_k\\} $  \n\n**Objective**  \nFor each test case $ k $, compute the number of distinct unordered triples $ \\{x, y, z\\} \\subseteq A_k $ with $ x \\le y \\le z $ such that the triangle inequality holds:  \n$$\nx + y > z\n$$","simple_statement":"Given N line segments, count how many distinct triangles can be formed, where a triangle is valid if the sum of the two smaller sides is greater than the largest side, and triangles are distinct if their three side lengths are different sets.","has_page_source":false}