The one who works is the one who eats... nothing

Time limit1sMemory limit256 MB

Summary

Given the worker has finished p percent of the job and eaten q percent of the food, find the minimum number of helpers, each a times faster and b times slower eaters, to finish before food runs out, or -1.

Level: Medium4 of 10
Topics: Math, Binary search, Implementation, Greedy
Solved: No attempts yet

Problem

Despite the saying <>, Mechnikov was forced to haul the theatrical props.

By the time he had finished $p$ percent of the task, the manager of the theater realized they did not have enough provision to feed the worker until he finished the work. Mechnikov ate $q$ percent of the received provision, with $q$ greater than $p$ .

That is when the manager, by slightly altering the popular motto <>, came up with <> (or almost nothing). For this reason, he decided to assign some free workforce to the toiling proletarian: a few coders who work for food. Each of the coders works $a$ times faster than the electrician and eats $b$ times slower.

The supply of free coders is virtually unlimited, but there is no reason to get too many of them. What if this becomes news and a great crowd of them arrives, craving free food? Help the manager to find the smallest necessary number of coders sufficient to make the available provision last until the work is finished.

Input

The first line of the input file contains a single number $t$ ( $1 \leq t \leq 3 \cdot 10^4$ ), the number of tests. Each of the following $t$ lines of the input file contains four integers $0 < p, q, a, b < 100$ , denoting, correspondingly, the percentage of completed work, the percentage of consumed provision, and how many times faster a coder works, and how many times slower he eats. It is guaranteed that $q > p$ .

Output

As an answer to each of $t$ tests, print a single integer: the minimum number of coders necessary to do the job. If it is impossible to complete the work, print -1.

Examples1

Example 1
Input
```
3
1 2 99 1
30 60 2 2
30 80 1 2
```
Expected output
```
1
10
-1
```