Milly is standing at the centre of a circle made by her friends. There are N people standing in a circle facing towards Milly as shown below. 2^nd person is at the left of the 1^st person and right of the 3^rd one. Similarly N^th person ia at the right of the 1^st person and at the left of the (N-1)^th person. Milly has K balls initially with her. She starts from the 1^st person's position and move in a clock-wise order. She will give i balls to every i^th person of this circle. She wants to complete the circle fully which means that if at some instant she is not able to give the balls due to lack of required number of balls then she will require some P number of additional balls in order to complete the circle and then she will stop.

Note : Milly can complete the circle any number of time till she has the required number of balls but once it is not possible to give the balls as per the requirement then she will take those P additional balls to complete the circle and then she will stop. If she is able to complete the circle some number of times using those K balls then she will not require any additional balls.

Input

• First line of the input will contain a integer T (number of test cases).
• Then for every test case there will be one line containing two space separated integers N and K.

Output

• For every test case, print the value of P in a new line.

Constraints

• 1 ≤ T ≤ 10⁵
• 1 ≤ N ≤ 10⁹
• 0 ≤ K ≤ 10⁹