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 nonnegative 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<=10^{5}) denoting the number of test cases. Each test case contains three integers a, b, and c. (1<=a, b, c<=10^{6}).
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 
Case 1: Yes 
Problem Setter: Md Abdul Alim, CEO and Founder at CodeMask
hide comments
anubhav1772:
20170714 14:25:41
Bézout's identity :) 

singlasahil221:
20170711 07:51:49
AC in one go. Easy one 

heisenberg0820:
20170702 10:21:11
My nth..


dangerous321:
20170629 14:23:19
how to print output


imsaral:
20170529 21:22:50
AC in one go :)


jainsahil1997:
20170523 07:19:29
Don't forget to add space between : and "yes" or "no" 

shivamarya_123:
20170429 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:
20170429 15:13:27
i didn't understood input/output format.


namitp:
20170411 18:41:20
very easy AC in one go...! 

lonelybanboo:
20170331 16:36:47
Gcd is enough. 
Added by:  Md Abdul Alim 
Date:  20141015 
Time limit:  3s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 GOSU 
Resource:  Own Problem 