Cable Cleanup

Time limit1sMemory limit256 MB

Summary

For each test case, keep N minus 1 of the M cables that join N computers into one network and print how many cables go.

Level: Easy3 of 10
Topics: Graph, Math
Solved: No attempts yet

Problem

At an ICPC regional contest, the operations team arrived at the site and only then found that the network of the contestant computers had been wired incorrectly. A large number of unneeded cables had been installed between the computers.

Abdelrahman, the director of operations, wants to remove as many cables as he can so that a runner is less likely to trip over one. Every computer still has to be reachable from every other computer after the removal. In the initial state all computers are reachable from each other.

Two computers are reachable from each other if a cable connects them directly. They are also reachable from each other if both of them are reachable from some third computer.

Find the maximum number of cables that can be removed.

Input

The first line contains the number of test cases $T$ , where $1 \le T \le 100$ .

Each of the following $T$ lines holds one test case: two integers $N$ and $M$ separated by a single space, where $N$ is the number of computers in the contest hall and $M$ is the number of cables. The bounds are $1 \le N \le 10^4$ and $N - 1 \le M \le 10^5$ .

The input does not say which computers each cable connects. It only guarantees that in the initial state all computers are reachable from each other.

Output

For each test case, print one line in the form Case n: R. Here $n$ is the test case number starting from 1, and $R$ is the maximum number of cables that can be removed.

Examples5

Example 1
Input
```
1
4 5
```
Expected output
```
Case 1: 2
```
Example 2
Input
```
1
1 0
```
Expected output
```
Case 1: 0
```
Example 3
Input
```
1
2 1
```
Expected output
```
Case 1: 0
```
Example 4
Input
```
1
3 3
```
Expected output
```
Case 1: 1
```

Example 5

Input

Expected output

Case 1: 0
Case 2: 5
Case 3: 0