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 8
3 6 7

Case 1: Yes
Case 2: No

Problem Setter: Md Abdul Alim, Dept. of Computer Science, Bangladesh University of Business & Technology


hide comments
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 :)

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"


Added by:Alim
Date:2014-10-15
Time limit:3s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU
Resource:Own Problem