## 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 cubalgo: 2016-08-07 01:30:15 note space between : and Yes/No . shashisuman: 2016-07-08 00:50:13 question is wrong a b and c can be negative ....heres its give a>=1 WTF got ac taking as -ve too siddharth_0196: 2016-06-11 12:13:46 easy. :) mkfeuhrer: 2016-06-08 12:50:22 hell to output format.....WA for dat ...take care .... easy othrwise :-) Sarthak Munshi: 2016-06-04 12:39:52 3 lines in python ! ashiq_iqbal: 2016-04-07 10:12:01 I think you should familiar with diophantine equation to solve this problem :) 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