문제<\/h2>
Let's say that three segments on a plane form a K-shaped figure<\/em> if:<\/p>

two of them share a common endpoint;<\/li>
this common endpoint lies strictly inside the third segment;<\/li>
these two segments are located on the same side with respect to the third one;<\/li>
all three segments are pairwise not collinear.<\/li> <\/ul>

[이미지 1]<\/span><\/td> [이미지 2]<\/span><\/td> [이미지 3]<\/span><\/td> [이미지 4]<\/span><\/td> [이미지 5]<\/span><\/td> [이미지 6]<\/span><\/td> [이미지 7]<\/span><\/td> <\/tr>
${<\/mo>A<\/mi>B<\/mi>,<\/mo>C<\/mi>D<\/mi>,<\/mo>C<\/mi>E<\/mi>}<\/mo><\/mrow>\{AB,CD,CE\}<\/math><\/span><\/span> {<\/span> A<\/span> B<\/span>,<\/span> <\/span> C<\/span> D<\/span>,<\/span> <\/span> C<\/span> E<\/span>}<\/span><\/span><\/span><\/span><\/td>$ ${<\/mo>A<\/mi>B<\/mi>,<\/mo>C<\/mi>D<\/mi>,<\/mo>C<\/mi>E<\/mi>}<\/mo><\/mrow>\{AB,CD,CE\}<\/math><\/span><\/span> {<\/span> A<\/span> B<\/span>,<\/span> <\/span> C<\/span> D<\/span>,<\/span> <\/span> C<\/span> E<\/span>}<\/span><\/span><\/span><\/span><\/td>$ ${<\/mo>A<\/mi>B<\/mi>,<\/mo>C<\/mi>D<\/mi>,<\/mo>C<\/mi>E<\/mi>}<\/mo><\/mrow>\{AB,CD,CE\}<\/math><\/span><\/span> {<\/span> A<\/span> B<\/span>,<\/span> <\/span> C<\/span> D<\/span>,<\/span> <\/span> C<\/span> E<\/span>}<\/span><\/span><\/span><\/span><\/td>$ ${<\/mo>A<\/mi>B<\/mi>,<\/mo>C<\/mi>D<\/mi>,<\/mo>C<\/mi>E<\/mi>}<\/mo><\/mrow>\{AB,CD,CE\}<\/math><\/span><\/span> {<\/span> A<\/span> B<\/span>,<\/span> <\/span> C<\/span> D<\/span>,<\/span> <\/span> C<\/span> E<\/span>}<\/span><\/span><\/span><\/span><\/td>$ ${<\/mo>A<\/mi>B<\/mi>,<\/mo>C<\/mi>D<\/mi>,<\/mo>C<\/mi>E<\/mi>}<\/mo><\/mrow>\{AB,CD,CE\}<\/math><\/span><\/span> {<\/span> A<\/span> B<\/span>,<\/span> <\/span> C<\/span> D<\/span>,<\/span> <\/span> C<\/span> E<\/span>}<\/span><\/span><\/span><\/span><\/td>$ ${<\/mo>A<\/mi>B<\/mi>,<\/mo>C<\/mi>D<\/mi>,<\/mo>E<\/mi>F<\/mi>}<\/mo><\/mrow>\{AB,CD,EF\}<\/math><\/span><\/span> {<\/span> A<\/span> B<\/span>,<\/span> <\/span> C<\/span> D<\/span>,<\/span> <\/span> E<\/span> F<\/span>}<\/span><\/span><\/span><\/span><\/td>$ ${<\/mo>A<\/mi>B<\/mi>,<\/mo>A<\/mi>C<\/mi>,<\/mo>A<\/mi>D<\/mi>}<\/mo><\/mrow>\{AB,AC,AD\}<\/math><\/span><\/span> {<\/span> A<\/span> B<\/span>,<\/span> <\/span> A<\/span> C<\/span>,<\/span> <\/span> A<\/span> D<\/span>}<\/span><\/span><\/span><\/span><\/td>
<\/tr>$
Valid K-shaped figures<\/td> Invalid K-shaped figures<\/td> <\/tr> <\/tbody> <\/table>
You are given a collection of $n<\/mi><\/mrow>n<\/math><\/span><\/span> n<\/span><\/span><\/span><\/span> segments on the plane. Find the number of triples of segments from this collection that form a K-shaped figure.<\/p> 입력<\/h2> Each test contains multiple test cases. The first line contains the number of test cases t<\/mi><\/mrow>t<\/math><\/span><\/span> t<\/span><\/span><\/span><\/span> (1<\/mn>\leq<\/mo>t<\/mi>\leq<\/mo>3333<\/mn><\/mrow>1 \le t \le 3333<\/math><\/span><\/span> 1<\/span> <\/span> \leq<\/span> <\/span><\/span> <\/span> t<\/span> <\/span> \leq<\/span> <\/span><\/span> <\/span> 3333<\/span><\/span><\/span><\/span>). The description of the test cases follows.<\/p> The first line of each test case contains a single integer n<\/mi><\/mrow>n<\/math><\/span>$

K-Shaped Figures