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<=10⁵) denoting the number of test cases. Each test case contains three integers a, b, and c. (1<=a, b, c<=10⁶).

Output

For each test case of input print the case number and “Yes” if there exists at least one solution, print “No” otherwise.

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