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


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

hide comments
2020-04-14 17:00:57
The output format is different follow the sample :).
You also need to update the case
Ex Case i: ans.

Last edit: 2020-04-14 17:04:41
2020-01-29 12:45:35
showing output is more difficult than to slove the qstn
2020-01-16 17:25:32
Diophantine equation-hint
2019-12-19 18:14:18
AC in one go!!!!!!!!
2019-12-13 08:13:21
follow the output format exactly costed me 2 wa..
2019-08-26 13:56:30
Hint is...
Find gcd of a and b..
If c%gcd ==0
Then yes otherwise no
2019-06-01 01:21:44
AC in one go
2019-04-15 12:16:02
Useful video for this question : https://www.youtube.com/watch?v=OrVWAYonFIU
2018-08-14 18:58:41
Use euclidean gcd!!
2018-08-14 18:57:55
AC in one go...!!!
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.