#12428Enemy at the Gates

The kingdom of ByteLand is in trouble. The enemies are going to attack ByteLand. The enemies know that ByteLand has exactly N cities and exactly M bidirectional roads and it is possible to go from any city to every other city directly or via other cities. They also know that any pair of cities can be directly connected by at most one road. But they do not have any information about which road connects which two cities. They are planning to destroy all critical roads of ByteLand. A road is critical if after destroying that road only at least one pair of cities become disconnected. They are very optimistic so they expect to destroy maximum number of critical roads. What is the maximum number of critical roads that can be present in ByteLand according only to the information the enemies have about ByteLand?

Input

The first line of input contains T (1 ≤ T ≤ 50) which is the number of tests cases. Each case contains two integers N and M, where N is the number of cities and M is the number of roads (2 ≤ N ≤ 10^5 and 1 ≤ M ≤ N(N-1)/2).

Output

For each test case output one integer the maximum number of critical roads that could be present in ByteLand.

Explanation of Sample Cases

2
4 4
4 3

1
3