X-Magic Pair

You are given a pair of integers (a,b) and an integer x.

You can change the pair in two different ways:

• set (assign) a:=|a−b|;
• set (assign) b:=|a−b|,

where |a−b| is the absolute difference between a and b.

The pair (a,b) is called x-magic if x is obtainable either as a or as b using only the given operations (i.e. the pair (a,b) is x-magic if a=x or b=x after some number of operations applied). You can apply the operations any number of times (even zero).

Your task is to find out if the pair (a,b) is x-magic or not.

You have to answer t independent test cases.

Input

The first line of the input contains one integer t (1≤t≤104) — the number of test cases. The next t lines describe test cases.

The only line of the test case contains three integers a, b and x (1≤a,b,x≤1018).

Output

For the i-th test case, print YES if the corresponding pair (a,b) is x-magic and NO otherwise.

Example

input

Copy

8
6 9 3
15 38 7
18 8 8
30 30 30
40 50 90
24 28 20
365 216 52
537037812705867558 338887693834423551 3199921013340

output

Copy

YES
YES
YES
YES
NO
YES
YES
YES

思路：这题的减法是取绝对值的，变换之后永远是正数，那么，我们可以一直将大的数减去小的数，这样便能跳过取绝对值的过程，取绝对值的过程就是大的减小的，所以用大的减小的便能模拟出所有的情况。所以只要x出现在a，b中能说明能够变成。但cf总会拐两个弯（对于人家不是，只是对于我这种垃圾而言）出现边界时（如 1，99999999）时，必会超时，那么就要优化了，我们举一个不太大的例子来模拟一下就会发现，一直减小的的过程中是一直重复的，如：（30，7）与（9，7）是一样的而且在下 一次的变化中，变成（2，7）更改了之后大小发生变化，在30变到9的过程中是一直减7的，且都比7的倍数多2，其实30与9是等价的，（30-9）%7==0，这样便能模拟出逐渐减7的过程，节省了很多步骤，大的数除余会得到更小的数，刚好得到变化之后较小的值，所以要在变化之前模拟减法的过程。

结论：除余能很好地优化减法的过程，不仅是（a-x）%b，而且还有大的数变成小的数的过程

除余1：除余的最大余数（除它本身）最大只能到 一半（奇数时，一半是向下取整）或一半减一（偶数时）即（n-1)/2。

除余2：当我们要求的某个数是由乘法与加法混合组成的，可以使用除余得出要加的数，用除法得出剩下的乘数。

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

typedef long long ll;

int main()
{
	int t;
	cin>>t;
	while(t--)
    {
        ll a,b,x;
        cin>>a>>b>>x;
        bool ok=true;
        while(a&&b)
        {
            if(a<b) swap(a,b);
            if(a==x||b==x)
            {
                ok=false;
                cout<<"YES"<<endl;
                break;
            }
            else if(x<=a&&(a-x)%b==0)
            {
                ok=false;
                cout<<"YES"<<endl;
                break;
            }
            a=a%b;
        }
        if(ok) cout<<"NO"<<endl;
    }
	return 0;
}