## CEQU - Crucial Equation

Let us see the following equation,

ax+by=c

Given three positive integers a, b and c. You have to determine whether there exists at least one solution for some integers value of x and y where x, y may be negative or non-negative integers.

For example if a=2, b=4 and c=8 then the equation will be 2x+4y=8, and hence, for x=2 and y=1, there exists a solution.

Let us see another example for a=3, b=6 and c=7, so the equation will become 3x+6y=7 and there exists no solution satisfying this equation.

Input

Input starts with an integer T (1<=T<=105) denoting the number of test cases. Each test case contains three integers a, b, and c. (1<=a, b, c<=106).

Output

For each test case of input print the case number and “Yes” if there exists at least one solution, print “No” otherwise.

 Sample Input Output for Sample Input 2 2 4 83 6 7 Case 1: Yes Case 2: No

Problem Setter: Md Abdul Alim, CEO and Founder at CodeMask

 < Previous 1 2 3 4 5 6 Next > surya8127: 2019-08-26 13:56:30 Hint is... Find gcd of a and b.. If c%gcd ==0 Then yes otherwise no aryan29: 2019-06-01 01:21:44 AC in one go cenation092: 2019-04-15 12:16:02 Useful video for this question : https://www.youtube.com/watch?v=OrVWAYonFIU mynk322: 2018-08-14 18:58:41 Use euclidean gcd!! mynk322: 2018-08-14 18:57:55 AC in one go...!!! ankur314: 2018-06-24 13:28:37 the basic-most question of diophantine equation. jmr99: 2018-06-20 19:46:39 follow the oupt frmt!! akash13s: 2018-06-08 07:51:06 Take care of how to print the output! jayharsh: 2017-08-12 07:50:25 AC in one go!........ anubhav1772: 2017-07-14 14:25:41 Bézout's identity :)