## 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 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. Shashank Tiwari: 2015-07-13 09:54:50 https://en.wikipedia.org/wiki/B%C3%A9zout%27s_identity Rishabh Joshi: 2015-06-11 20:23:45 elementary. :) Addy: 2015-05-31 22:06:36 Any hints please? __hk__: 2015-05-31 14:37:10 @narendra pal: yes....as it is given x,y can be negative and "non-negative" integers , zero includes in 2nd category...