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. Success Rate

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou are an experienced Codeforces user. Today you found out that during your activity on Codeforces you have made *y* submissions, out of which *x* have been successful. Thus, your current success rate on Codeforces is equal to *x* / *y*.

Your favorite rational number in the [0;1] range is *p* / *q*. Now you wonder: what is the smallest number of submissions you have to make if you want your success rate to be *p* / *q*?

Input

The first line contains a single integer *t* (1 ≤ *t* ≤ 1000) — the number of test cases.

Each of the next *t* lines contains four integers *x*, *y*, *p* and *q* (0 ≤ *x* ≤ *y* ≤ 10^{9}; 0 ≤ *p* ≤ *q* ≤ 10^{9}; *y* > 0; *q* > 0).

It is guaranteed that *p* / *q* is an irreducible fraction.

Hacks. For hacks, an additional constraint of *t* ≤ 5 must be met.

Output

For each test case, output a single integer equal to the smallest number of submissions you have to make if you want your success rate to be equal to your favorite rational number, or -1 if this is impossible to achieve.

Example

Input

4

3 10 1 2

7 14 3 8

20 70 2 7

5 6 1 1

Output

4

10

0

-1

Note

In the first example, you have to make 4 successful submissions. Your success rate will be equal to 7 / 14, or 1 / 2.

In the second example, you have to make 2 successful and 8 unsuccessful submissions. Your success rate will be equal to 9 / 24, or 3 / 8.

In the third example, there is no need to make any new submissions. Your success rate is already equal to 20 / 70, or 2 / 7.

In the fourth example, the only unsuccessful submission breaks your hopes of having the success rate equal to 1.

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/13/2018 19:56:24 (f2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|