The great king Gymman and his queen Asira were living together happily. But an evil magician the evil Fila, who is trying to get hold of the throne had made a plan to separate the king and queen to get hold of the throne. There were many cities in the kingdom. All of them were connected with bidirectional roads. He planned to send the king and queen into two different cities giving wrong messages, as without the queen, king would be very sad and unable to continue ruling. The evil fila succeeded on his task, as king and queen are not evil and they believed him. Though now king and queen lives in different city they frequently communicate with each other. The communication took place through letters and to exchange letters in kingdom the two corresponding cities should be connected through one or more bidirectional roads. After the separation of king and queen, a natural calamity came into the kingdom and destroyed some of the bidirectional roads. If the king and queen still can communicate with each other Fila have to block communication between them. But he can occupy only one city and siege the letter carrier. King got this information of the evil plan. Now he wants to know according to Fila’s plan how many different combination of 3 cities a, b, c (a ̸= b ̸= c) exists such that king will be on city a, queen will be on city b and evil Fila will be on city c and Fila can block communication between king and queen. Two combinations (x1,y1,z1) and (x2,y2,z2) will be same if x1 and x2 are same, y1 and y2 are same and z1 and z2 are same. As Fila is an evil magician, he can go to any city with his magical power without the help of road transports. Input First line contains T (1 < T < 21), the number of test cases to follow. For each test case, in the 1st line there will be 2 integers N (1 ≤ N ≤ 20000) and M (0 ≤ M ≤ 100000). N is the number of cities and M is the number of roads between them. M lines follow, each containing two integers u and v. That means there is a bidirectional road between city u and city v. The cities are numbered from 1 to N. All roads will be distinct and connect two different cities. Output For each case, print the test case number starting from 1 and the number of combinations in one line. See sample output for exact formatting. Explanation: In 2-nd test case, 4 triplets are (1, 2, 3), (1, 4, 3), (2, 1, 3) and (4, 1, 3). In 3-rd test case, 2 triplets are (4, 6, 5) and (6, 4, 5). Sample Input 3 33 12 23 13 44 24
2/2 43 23 31 65 12 23 13 45 56 Sample Output Case 1: 0 Case 2: 4 Case 3: 2