Rishi lives in Area 51. In Area 51, there are n shops numbered from 1 to n and at the end of n shops, there is a cash counter. When he goes to shop numbered i he makes a purchase of exactly i Rupees. There is a special rule in Area 51 that instead of adding individual costs to obtain the total cost made from multiple shops, we multiply them which means if he purchased items worth 2, 3 and 4 from 3 shops respectively, the total cost becomes 2*3*4=24. All the payments made for any purchase from one or more shops is made only at the cash counter.

One day Rishi went to the market and made purchases from each of the n shops of the market. But now Rishi has a dilemma standing at the cash counter, he has unlimited supply of Rupees X coins only. He paid the total cost by using the minimum number of Rupees X coins and asked them to keep the change if any. As he always keeps a record of his charity he is now interested in knowing how much he has tipped the shopkeepers of the market. Help him determine the amount of charity he did.

Input:

In the 1st line, you will be given the number of test cases t. Each of the next t lines contains two integers n and X.

Output:

Print in new line the amount of charity he did.

Constraints:

1<=t<=50

1<=n<=10^9

1<=X<=10^5