{"raw_statement":[{"iden":"statement","content":"You 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_.\n\nYour 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_?"},{"iden":"input","content":"The first line contains a single integer _t_ (1 ≤ _t_ ≤ 1000) — the number of test cases.\n\nEach of the next _t_ lines contains four integers _x_, _y_, _p_ and _q_ (0 ≤ _x_ ≤ _y_ ≤ 109; 0 ≤ _p_ ≤ _q_ ≤ 109; _y_ > 0; _q_ > 0).\n\nIt is guaranteed that _p_ / _q_ is an irreducible fraction.\n\n**Hacks.** For hacks, an additional constraint of _t_ ≤ 5 must be met."},{"iden":"output","content":"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."},{"iden":"example","content":"Input\n\n4\n3 10 1 2\n7 14 3 8\n20 70 2 7\n5 6 1 1\n\nOutput\n\n4\n10\n0\n-1"},{"iden":"note","content":"In the first example, you have to make 4 successful submissions. Your success rate will be equal to 7 / 14, or 1 / 2.\n\nIn 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.\n\nIn the third example, there is no need to make any new submissions. Your success rate is already equal to 20 / 70, or 2 / 7.\n\nIn the fourth example, the only unsuccessful submission breaks your hopes of having the success rate equal to 1."}],"translated_statement":[{"iden":"statement","content":"你是一位经验丰富的 Codeforces 用户。今天你发现，在你于 Codeforces 上的活动中，你一共提交了 #cf_span[y] 次，其中 #cf_span[x] 次成功。因此，你在 Codeforces 上的当前成功率是 #cf_span[x / y]。\n\n你最喜欢的区间 #cf_span[[0;1]] 内的有理数是 #cf_span[p / q]。现在你想知道：为了让你的成功率变为 #cf_span[p / q]，你最少需要再提交多少次？\n\n第一行包含一个整数 #cf_span[t] (#cf_span[1 ≤ t ≤ 1000]) —— 测试用例的数量。\n\n接下来的 #cf_span[t] 行，每行包含四个整数 #cf_span[x], #cf_span[y], #cf_span[p] 和 #cf_span[q] (#cf_span[0 ≤ x ≤ y ≤ 10^9]；#cf_span[0 ≤ p ≤ q ≤ 10^9]；#cf_span[y > 0]；#cf_span[q > 0])。\n\n保证 #cf_span[p / q] 是一个最简分数。\n\n*黑客测试*。对于黑客测试，必须满足额外约束 #cf_span[t ≤ 5]。\n\n对于每个测试用例，输出一个整数，表示你为了使成功率等于你最喜欢的有理数所需做的最少提交次数；如果无法实现，则输出 _-1_。\n\n在第一个例子中，你需要再做 4 次成功提交。你的成功率将变为 #cf_span[7 / 14]，即 #cf_span[1 / 2]。\n\n在第二个例子中，你需要再做 2 次成功提交和 8 次失败提交。你的成功率将变为 #cf_span[9 / 24]，即 #cf_span[3 / 8]。\n\n在第三个例子中，无需做任何新提交。你的成功率已经是 #cf_span[20 / 70]，即 #cf_span[2 / 7]。\n\n在第四个例子中，唯一的失败提交破坏了你获得成功率为 1 的希望。"},{"iden":"input","content":"第一行包含一个整数 #cf_span[t] (#cf_span[1 ≤ t ≤ 1000]) —— 测试用例的数量。接下来的 #cf_span[t] 行，每行包含四个整数 #cf_span[x], #cf_span[y], #cf_span[p] 和 #cf_span[q] (#cf_span[0 ≤ x ≤ y ≤ 10^9]；#cf_span[0 ≤ p ≤ q ≤ 10^9]；#cf_span[y > 0]；#cf_span[q > 0])。保证 #cf_span[p / q] 是一个最简分数。*黑客测试*。对于黑客测试，必须满足额外约束 #cf_span[t ≤ 5]。"},{"iden":"output","content":"对于每个测试用例，输出一个整数，表示你为了使成功率等于你最喜欢的有理数所需做的最少提交次数；如果无法实现，则输出 _-1_。"},{"iden":"note","content":"在第一个例子中，你需要再做 4 次成功提交。你的成功率将变为 #cf_span[7 / 14]，即 #cf_span[1 / 2]。在第二个例子中，你需要再做 2 次成功提交和 8 次失败提交。你的成功率将变为 #cf_span[9 / 24]，即 #cf_span[3 / 8]。在第三个例子中，无需做任何新提交。你的成功率已经是 #cf_span[20 / 70]，即 #cf_span[2 / 7]。在第四个例子中，唯一的失败提交破坏了你获得成功率为 1 的希望。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ t \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case $ k \\in \\{1, \\dots, t\\} $, let:  \n- $ x_k, y_k \\in \\mathbb{Z}_{\\geq 0} $ with $ 0 \\leq x_k \\leq y_k $,  \n- $ p_k, q_k \\in \\mathbb{Z}_{\\geq 0} $ with $ 0 \\leq p_k \\leq q_k $, $ q_k > 0 $,  \n- $ \\frac{p_k}{q_k} $ be an irreducible fraction.\n\n**Constraints**  \n1. $ 1 \\leq t \\leq 1000 $  \n2. $ 0 \\leq x_k \\leq y_k \\leq 10^9 $  \n3. $ 0 \\leq p_k \\leq q_k \\leq 10^9 $, $ q_k > 0 $  \n4. $ \\gcd(p_k, q_k) = 1 $\n\n**Objective**  \nFind the smallest non-negative integer $ d $ such that there exist non-negative integers $ a, b $ with:  \n$$\nx_k + a = p_k \\cdot n, \\quad y_k + a + b = q_k \\cdot n\n$$  \nfor some integer $ n \\geq 1 $, and $ a \\geq 0 $, $ b \\geq 0 $,  \nor output $ -1 $ if no such $ d = a + b $ exists.\n\nEquivalently, find the minimal $ d \\geq 0 $ such that:  \n$$\n\\exists n \\in \\mathbb{Z}^+, \\quad x_k \\leq p_k n, \\quad y_k \\leq q_k n, \\quad p_k n - x_k \\leq q_k n - y_k\n$$  \nand $ d = (q_k n - y_k) $.  \n\nAlternatively, minimize $ d = q_k n - y_k $ over integers $ n \\geq \\max\\left( \\left\\lceil \\frac{x_k}{p_k} \\right\\rceil, \\left\\lceil \\frac{y_k}{q_k} \\right\\rceil \\right) $ (with $ p_k > 0 $), under the constraint $ p_k n - x_k \\leq q_k n - y_k $, and if $ p_k = 0 $, then $ x_k = 0 $ must hold.  \n\nIf $ p_k = 0 $ and $ x_k > 0 $, output $ -1 $.","simple_statement":null,"has_page_source":false}