链接: https://cses.fi/problemset/task/3214

板块: Additional Problems I

时限: 1.00 s ｜ 内存: 512 MB

题目描述

有两个水容器：容器 A 的容积为 $a$，容器 B 的容积为 $b$。你想用这些容器量出 $x$ 单位的水。

初始时两个容器都为空。每一步，你可以装满一个容器、倒空一个容器，或将水从一个容器移到另一个容器。当你移动水时，必须至少装满或倒空一个容器。移动结束后，容器 A 必须装有 $x$ 单位的水。

你的任务是高效地判断在多种情况下是否能量出该水量。

输入

第一行包含整数 $n$：测试的数量。

接下来有 $n$ 行。每行包含三个整数 $a$、$b$ 和 $x$。

输出

对于每个测试，如果能量出该水量则输出 YES，否则输出 NO。

数据范围

$1 \le n \le 1000$ $1 \le a, b, x \le 10^9$

样例输入

7
5 3 4
1 1 1
1 1 2
2 2 1
123 456 42
1000 999 123
1000 998 123

样例输出

YES
YES
NO
NO
YES
YES
NO