CRAZYSK - Crazy Shopkeeper

no tags 

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

hide comments
Divyank Duvedi: 2014-06-13 04:16:25

the constraint X<=2^64 made the question a little bit tougher.
Even unsigned long long won't work (bcox max limit is 2^64-1)

Bhavik: 2013-12-27 16:51:02

not a single AC solution in C!!!!why is that??unfair for C users...had to use java for this

Last edit: 2013-12-27 17:09:50
Vaibhav Gupta: 2013-10-30 19:52:28

@wasi: i m getting nzec !!!
can u help plz...!!
edit : accepted :)

Last edit: 2013-10-30 20:00:32
Martijn Muijsers: 2013-10-23 16:47:30

Cool problem! I made a lot of mistakes while doing this, luckily I caught most of them with pen and paper ;D


Added by:ওয়াসী (Wasi)
Date:2013-05-07
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:ADA95 ASM32 GAWK BASH BF C CSHARP C++ 4.3.2 CPP C99 CLPS CLOJURE LISP sbcl LISP clisp D ERL FSHARP FORTRAN GO HASK ICON ICK JAVA JS-RHINO LUA NEM NICE NODEJS OCAML PAS-GPC PAS-FPC PDF PERL PERL6 PHP PIKE PS PRLG-swi PYTHON PYTHON3 PY_NBC RUBY
Resource:own problem