310749: CF1881B. Three Threadlets

B. Three Threadletstime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

Once upon a time, bartender Decim found three threadlets and a pair of scissors.

In one operation, Decim chooses any threadlet and cuts it into two threadlets, whose lengths are positive integers and their sum is equal to the length of the threadlet being cut.

For example, he can cut a threadlet of length $5$ into threadlets of lengths $2$ and $3$, but he cannot cut it into threadlets of lengths $2.5$ and $2.5$, or lengths $0$ and $5$, or lengths $3$ and $4$.

Decim can perform at most three operations. He is allowed to cut the threadlets obtained from previous cuts. Will he be able to make all the threadlets of equal length?

Input

The first line contains an integer $t$ ($1 \le t \le 10^4$) — the number of test cases. Then follows the description of each test case.

In a single line of each test case, there are three integers $a$, $b$, $c$ ($1 \le a, b, c \le 10^9$) — the lengths of the threadlets.

Output

For each test case, output "YES" if it is possible to make all the threadlets of equal length by performing at most three operations, otherwise output "NO".

You can output "YES" and "NO" in any case (for example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as a positive answer).

ExampleInput

15
1 3 2
5 5 5
6 36 12
7 8 7
6 3 3
4 4 12
12 6 8
1000000000 1000000000 1000000000
3 7 1
9 9 1
9 3 6
2 8 2
5 3 10
8 4 8
2 8 4

Output

YES
YES
NO
NO
YES
YES
NO
YES
NO
NO
YES
YES
NO
YES
NO

Note

Let's consider some testcases of the first test.

In the first testcase, you can apply following operations:

$1, 3, 2 \to 1, 2, 1, 2 \to 1, 1, 1, 1, 2 \to 1, 1, 1, 1, 1, 1$.

In the second testcase, you can do nothing, the threadlets are already of equal length.

In the third testcase, it isn't possible to make threadlets of equal length.

题目大意：
Decim 有三根线段和一把剪刀。每次操作，他可以选择一根线段，将其切成两段，这两段线段的长度必须是正整数，且它们的和等于被切线段的长度。Decim 最多进行三次操作，他也可以切割之前切割得到的线段。问是否可能通过这些操作使得所有线段长度相等。

输入数据格式：
第一行包含一个整数 t（1 ≤ t ≤ 10^4），表示测试用例的数量。接下来是每个测试用例的描述。
每个测试用例在一行内包含三个整数 a, b, c（1 ≤ a, b, c ≤ 10^9），分别表示三根线段的长度。

输出数据格式：
对于每个测试用例，如果可能通过最多三次操作使得所有线段长度相等，则输出 "YES"，否则输出 "NO"。
输出 "YES" 和 "NO" 时大小写不敏感。

例如：
输入：
15
1 3 2
5 5 5
6 36 12
7 8 7
6 3 3
4 4 12
12 6 8
1000000000 1000000000 1000000000
3 7 1
9 9 1
9 3 6
2 8 2
5 3 10
8 4 8
2 8 4

输出：
YES
YES
NO
NO
YES
YES
NO
YES
NO
NO
YES
YES
NO
YES
NO

注意：
- 在第一个测试用例中，可以通过以下操作使得线段长度相等：1, 3, 2 → 1, 2, 1, 2 → 1, 1, 1, 1, 2 → 1, 1, 1, 1, 1, 1。
- 在第二个测试用例中，线段已经是等长的，不需要操作。
- 在第三个测试用例中，不可能使得线段长度相等。题目大意： Decim 有三根线段和一把剪刀。每次操作，他可以选择一根线段，将其切成两段，这两段线段的长度必须是正整数，且它们的和等于被切线段的长度。Decim 最多进行三次操作，他也可以切割之前切割得到的线段。问是否可能通过这些操作使得所有线段长度相等。 输入数据格式： 第一行包含一个整数 t（1 ≤ t ≤ 10^4），表示测试用例的数量。接下来是每个测试用例的描述。 每个测试用例在一行内包含三个整数 a, b, c（1 ≤ a, b, c ≤ 10^9），分别表示三根线段的长度。 输出数据格式： 对于每个测试用例，如果可能通过最多三次操作使得所有线段长度相等，则输出 "YES"，否则输出 "NO"。 输出 "YES" 和 "NO" 时大小写不敏感。 例如： 输入： 15 1 3 2 5 5 5 6 36 12 7 8 7 6 3 3 4 4 12 12 6 8 1000000000 1000000000 1000000000 3 7 1 9 9 1 9 3 6 2 8 2 5 3 10 8 4 8 2 8 4 输出： YES YES NO NO YES YES NO YES NO NO YES YES NO YES NO 注意： - 在第一个测试用例中，可以通过以下操作使得线段长度相等：1, 3, 2 → 1, 2, 1, 2 → 1, 1, 1, 1, 2 → 1, 1, 1, 1, 1, 1。 - 在第二个测试用例中，线段已经是等长的，不需要操作。 - 在第三个测试用例中，不可能使得线段长度相等。