A clique in a graph is set of nodes such that there is an edge between any two distinct nodes in the set. It is well known that finding the largest clique in a graph is a computationally tough problem and no polynomial time algorithm is known for it. However, you wonder what is is the mininum size of the largest clique in any graph with N nodes and M edges. Of course, the graph should have at most one edge between any two nodes and no edges connecting a node to itself.

Input

The first line contains T the number of test cases. Each of the next T lines contain 2 integers N and M.

Output

Output T lines, one for each test case, containing the desired answer for the corresponding test case.

Example

Input:
3
3 2
4 6
5 7

Output:
2
4
3

Constraints

1 ≤ T ≤ 100000

2 ≤ N ≤ 10000

1 ≤ M ≤ N*(N-1)/2

Explanation

For the second test case, the only valid graph having 4 nodes and 6 edges is one where each pair of nodes is connected. So the size of the largest clique cannot be smaller than 4.

For the third test case, it is easy to verify that any graph with 5 nodes and 7 edges will surely have a clique of size 3 or more.