## 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 anubhav1772: 2017-07-14 14:25:41 Bézout's identity :) singlasahil221: 2017-07-11 07:51:49 AC in one go. Easy one heisenberg0820: 2017-07-02 10:21:11 My nth.. AC in one go :D dangerous321: 2017-06-29 14:23:19 how to print output imsaral: 2017-05-29 21:22:50 AC in one go :) My 50th !! :D jainsahil1997: 2017-05-23 07:19:29 Don't forget to add space between : and "yes" or "no" shivamarya_123: 2017-04-29 15:16:02 there is only two cases case 1 and case 2 or more,and space between case and 1 or not. shivamarya_123: 2017-04-29 15:13:27 i didn't understood input/output format. namitp: 2017-04-11 18:41:20 very easy AC in one go...! lonelybanboo: 2017-03-31 16:36:47 Gcd is enough.