I want to eat chicken

Time limit1sMemory limit256 MB

Summary

Each person buys as many chickens as his money allows; compute how many more Sangeon eats than Dooyoung given coupon rules.

Level: Medium4 of 10
Topics: Math, Simulation, Implementation
Solved: No attempts yet

Problem

Building 301 at Seoul National University hides a fried chicken shop called Nupchicken. Every time you order a chicken there, the shop hands you $C$ coupons, and $F$ coupons buy one free chicken.

Dooyoung is not a regular, so a chicken he orders with coupons comes with no coupons at all. Sangeon is a regular, and the owner gives him coupons even for a chicken ordered with coupons.

Sangeon and Dooyoung each have $M$ won, and one chicken costs $P$ won. Each of them orders as many chickens as his money allows and takes a free chicken every time he has collected $F$ coupons. Find how many more chickens Sangeon eats than Dooyoung.

Input

The first line contains the number of test cases $T$ ( $1 \le T \le 20{,}000$ ). The $T$ test cases follow.

Each test case is one line with four integers: the price of one chicken $P$ ( $1 \le P \le 50{,}000$ ), the money available for chicken $M$ ( $1 \le M \le 1{,}000{,}000$ ), the number of coupons needed for one free chicken $F$ ( $2 \le F \le 1{,}000$ ), and the number of coupons given for one ordered chicken $C$ ( $1 \le C < F$ ), in that order.

Output

For each test case, print on its own line how many more chickens Sangeon eats than Dooyoung.

Examples7

Example 1
Input
```
2
10000 50000 5 1
10000 250000 5 1
```
Expected output
```
0
1
```
Example 2
Input
```
1
50000 49999 2 1
```
Expected output
```
0
```
Example 3
Input
```
1
1 1 2 1
```
Expected output
```
0
```
Example 4
Input
```
1
100 500 5 1
```
Expected output
```
0
```
Example 5
Input
```
1
1 10 2 1
```
Expected output
```
4
```
Example 6
Input
```
1
50000 1000000 2 1
```
Expected output
```
9
```

Example 7

Input

4
7 100 3 2
1000 1000000 1000 999
25 25 4 3
13 999999 2 1

Expected output