Mohib() As we all known, is very brilliant in mathematics, his friend bar has given him another problem to solve. Bar gives him the sequence of distinct positive number, and then includes the number x in the sequence. The average of the numbers is avg. If bar removes the number x from the list, the new average is avg+1. He asked the Foo to tell him the largest possible number in the sequence.
Input
FirstLine contain number of testcases (t <=5000).
Next t lines contain the number x(1<=x<=49999) and avg(x+1<=avg<=50000).
Output
Print the largest possible number in the sequence.
Example
Input:
1
1 2
Output:
3