{"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} $ be the current number of successful and total submissions, respectively, with $ 0 \\leq x_k \\leq y_k $ and $ y_k > 0 $,  \n- $ p_k, q_k \\in \\mathbb{Z}_{\\geq 0} $ be the numerator and denominator of the target irreducible fraction, with $ 0 \\leq p_k \\leq q_k $ and $ q_k > 0 $.  \n\n**Constraints**  \n1. $ 1 \\leq t \\leq 1000 $  \n2. For each $ k $:  \n   - $ 0 \\leq x_k \\leq y_k \\leq 10^9 $  \n   - $ 0 \\leq p_k \\leq q_k \\leq 10^9 $  \n   - $ \\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- $ a \\geq 0 $: additional successful submissions,  \n- $ b \\geq 0 $: additional total submissions (so $ b \\geq a $),  \n- $ d = a + b $,  \n- $ \\frac{x_k + a}{y_k + b} = \\frac{p_k}{q_k} $.  \n\nIf no such $ d $ exists, output $ -1 $.  \n\nEquivalently, find the minimal $ d \\geq 0 $ such that:  \n$$\n\\exists \\, n \\in \\mathbb{Z}_{>0} \\text{ with } n p_k \\geq x_k, \\; n q_k \\geq y_k, \\; \\text{and} \\; d = n q_k - y_k\n$$  \nand $ n p_k - x_k \\leq n q_k - y_k $ (which is always true since $ p_k \\leq q_k $).  \n\nThus, minimize $ d = n q_k - 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) $ if $ p_k > 0 $, or if $ p_k = 0 $, then $ x_k = 0 $ and $ n \\geq \\left\\lceil \\frac{y_k}{q_k} \\right\\rceil $.  \n\nIf $ p_k = 0 $ and $ x_k > 0 $, output $ -1 $.  \nIf $ p_k = q_k $ and $ x_k < y_k $, output $ -1 $ (since we cannot reduce failure rate to 0).","simple_statement":null,"has_page_source":false}