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
try2catch: 2016-03-24 05:12:54

OMG! Java took 3.2s O_o

sharath_111: 2016-01-30 19:09:00

good one in basics...take care of output format cost me WA.. :)

crazy_coder97: 2016-01-17 20:17:34

output format costed me 3 wa :(

Last edit: 2016-01-17 20:21:49
rocode0001: 2015-12-23 11:37:27

Output format costed me 1 wrng ans!!!...be careful

kamran siddique: 2015-10-20 15:15:31

sifting colon right left right left.............Taking hell lot of time ....... @shantanu, Agreed.

arpit : 2015-10-11 20:45:42

leave a space after colon,cost me a wa

gaurav117: 2015-08-14 13:43:50

good problem to make it to 4 digit after 16 day streak.....;]

shantanu tripathi: 2015-08-10 18:34:27

should be moved to where..... yes in tutorials.. :P

alok singh: 2015-08-10 18:32:03

loved this..... one go...:P

MishThi: 2015-08-02 11:15:18

Based on Bezout's Identity.


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