Since Ramadan is here, Ali wants to give gifts to the children of his neighborhood.
Ali has $n$ bags of candies. Let $a_i$ be the number of candies in bag $i$. For each $i$ from $1$ to $n$ we know that $a_i = i$; meaning that each bag has the same number of candies as its order in the array.
Ali decided to give each child two bags instead of one. And in order to satisfy all of the children, he wants to give each one of them the same total number of candies, which he decided to be equal to $k$.
As you are a good friend to Ali, you told him that you can give him at most one more bag of candies and this bag can contain any number of candies from $1$ to $n$ as needed.
Now Ali wants to know the maximum number of children who will be satisfied after using the $(n+1)$ bags (he might use them all or only some of them).
Over $T$ test cases given $n$ and $k$, find the maximum number of satisfied children if Ali distributes the $(n + 1)$ bags in the optimal way.
The input consists of multiple test cases. The first line contains a single integer $t (1 \le t \le 10^4)$ --- the number of test cases.
Each test case has only one line containing two integers $n$ $(1 \le n \le 10^9)$ and $k$ $(1 \le k \le n+1)$ --- the number of the bags Ali originally has and the total number of candies he wants to give each child respectively
Print a single integer, the maximum number of satisfied children.
| Input | Output |
|---|---|
2 6 7 3 1 Copy
|
3 0 Copy
|
We can observe that all bags having $k$ or more candies are useless since we can't pair of any of them with any other bag and produce a sum of $k$ (the sum here will always be greater than $k$).
Now this leaves us with $k - 1$ bags having values from $1$ to $k - 1$, and we want to group them into pairs to get a sum equal to $k$ for each pair.
If that value ($k - 1$) is even, it means that we can group them perfectly into $\frac{k - 1}{2}$ pairs, such that the pairs are like $(1, k-1)$, $(2, k-2)$, and so on.. Thus, we can discard the extra bag in this case as we have no need for it.
But if the value ($k - 1$) is odd, it would mean that if we do the pairing as above, we'll end up having one extra unpaired element (the element $\frac{k}{2}$), which we can then make into a pair using our extra bag of candies (it'll also have $\frac{k}{2}$ candies in order for the sum to reach $k$).
So grouping both cases together, when we have $k-1$ bags to group, the answer will be $\lceil \frac{k - 1}{2}\rceil$, which is equal to $\frac{k}{2}$.