Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

A. Vasya and Chocolate

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputThere is a special offer in Vasya's favourite supermarket: if the customer buys $$$a$$$ chocolate bars, he or she may take $$$b$$$ additional bars for free. This special offer can be used any number of times.

Vasya currently has $$$s$$$ roubles, and he wants to get as many chocolate bars for free. Each chocolate bar costs $$$c$$$ roubles. Help Vasya to calculate the maximum possible number of chocolate bars he can get!

Input

The first line contains one integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of testcases.

Each of the next $$$t$$$ lines contains four integers $$$s, a, b, c~(1 \le s, a, b, c \le 10^9)$$$ — the number of roubles Vasya has, the number of chocolate bars you have to buy to use the special offer, the number of bars you get for free, and the cost of one bar, respectively.

Output

Print $$$t$$$ lines. $$$i$$$-th line should contain the maximum possible number of chocolate bars Vasya can get in $$$i$$$-th test.

Example

Input

2

10 3 1 1

1000000000 1 1000000000 1

Output

13

1000000001000000000

Note

In the first test of the example Vasya can buy $$$9$$$ bars, get $$$3$$$ for free, buy another bar, and so he will get $$$13$$$ bars.

In the second test Vasya buys $$$1000000000$$$ bars and gets $$$1000000000000000000$$$ for free. So he has $$$1000000001000000000$$$ bars.

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/11/2018 02:18:42 (d1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|