{"problem":{"name":"A. Success Rate","description":{"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 rat","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF806A"},"statements":[{"statement_type":"Markdown","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_?\n\n## Input\n\nThe 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.\n\n## Output\n\nFor 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.\n\n[samples]\n\n## Note\n\nIn 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.","is_translate":false,"language":"English"}],"meta":{"iden":"CF806A","tags":["binary search","math"],"sample_group":[["4\n3 10 1 2\n7 14 3 8\n20 70 2 7\n5 6 1 1","4\n10\n0\n-1"]],"created_at":"2026-03-03 11:00:39"}}