First Bad Version

You are a product manager and currently leading a team to develop a new version of a product. Unfortunately, the latest version you are working on fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.

Suppose you have an array of N versions [1, 2, ..., N] and you want to find out the first bad version, which causes all the succeeding versions to be bad.

Consider we have a function isBadVersion(version), this will return whether the version is bad or not.

For an example, suppose n = 5, and version = 4 is the first bad version. So if the isBadVersion(3) returns false, isBadVersion(5) returns true and isBadVersion(4) also returns true, then the first bad version is 4.

You should minimize the number of calls to the API.

Note :

bool isBadVersion(version) returns true for all versions ‘V’ such that V > X, where X is the first bad version.

Input format:

The first line of input contains an integer ‘T’ denoting the number of test cases.
Then the T test cases follow.

The first and only input line will have two space-separated integers N(total number of versions) and V(the first bad version). 

Output format:

For each test case, print a single line containing a single integer denoting the first bad version.

The output of each test case will be printed in a separate line. 

Note:

You do not need to print anything; it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 5
1 <= V <= N
1 <= N <= 100000

Where ‘T’ is the number of test cases, ‘N’ is the total number of versions we have, and ‘V’ is the version.

Time limit: 1 sec.