Zoglu Bepari is a peculiar shopkeeper of Chittagong. He is a very famous shopkeeper. Everyone loves him and gave him  a nick name ‘MAMU’. He has a beautiful small shop which is also known as “MAMUR DOKAN”. From morning to late night, he sells non-stop. His shop always remains over-crowded as he gives some weird and crazy offers almost every day. Most of the offers favor customers. He recently created a special offer for his customers. For each item he sells, he gives a special card. These cards are rare and only available in his shop. And no one can cheat with him showing fake cards as he is really good at checking cards. Suppose, a customer bought X items, he gives a positive number N along with X cards to the customer. Another important thing is customers can return N cards for collecting another item of same type and a card in exchange.

Now as a programmer, you just have to calculate the total number of items a customer can get after using maximum number of cards he gets.

Input

Input starts with an positive integer T < 100 followed by T lines. Each of these lines contain two positive integers, number of item (X) bought in the first deal 1 < X <= 2^64, and number(N) that is given by Mamu 1 < N <= X.

Output

Print the total number of items the customer will have after exchanging maximum number of cards for getting extra items.

Example

Input:
5
15 3
2147483647 2
34 3
231 2
5 2

Output:
22
4294967293
50
461
9