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
vineetjai: 2020-09-06 09:34:53

Tried to solve in C++ got WA, same solution works in Python

mag1x_: 2018-06-26 09:51:18

This one made me ditch C++ & go beg to python :3

Shubham Pandey: 2016-06-27 18:36:50

6 lines code in python , got 4 WAs in C++ probably due to overflow

utkarsh538: 2016-04-25 12:22:38

very simple logic :)

hodobox: 2016-02-02 02:17:20

I got confused by description, so if anyone else did as well, here's what it says:
At the start, the customer bought N items.
For each item he bought, he received 1 card.
For each X cards, the customer can buy 1 item, and receives 1 card back.
Find out how many items the customer can buy until he is left with less than X cards (meaning he can buy no more items)

sannihith kavala: 2015-08-15 14:43:01

50th A.C :) simple math

Abhilash: 2015-06-17 11:46:54

5 lines in Python

Anubhav Gupta: 2015-01-09 06:39:43

Use Biginteger to store n and x

sid: 2014-06-24 12:59:20

WA IN C++...
SAME ALGO GIVES AC IN PYTHON!!!

NAVNEET GUPTA : 2014-06-21 07:05:58

My first java solution... :)
logic is simple.....


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