Background

1s 256M

Problem Description

You have $10^{20}$ cells, numbered starting from $0$. Initially, all cells are uncolored. Now you color them according to the following rules:

1. Cells whose indices are multiples of $p_1$ (including cell $0$, same below) are colored red.
2. Cells whose indices are multiples of $p_2$ are colored blue.
3. For cells whose indices are multiples of both $p_1$ and $p_2$, you may choose to color them red or blue.

Here $p_1$ and $p_2$ are given integers. If a cell index is a multiple of $p_1$ or $p_2$, then it must be colored. After ignoring all uncolored cells, you do not want there to be $k$ consecutive cells with the same color, because you think such a coloring scheme is boring. Given $p_1$, $p_2$, and $k$, you want to know whether there exists a coloring scheme that is not boring.

Input Format

This problem contains multiple test cases.

The first line contains an integer $T$ indicating the number of test cases.

Each test case consists of one line with three positive integers $p_1$, $p_2$, $k$, with meanings as described above.

Output Format

For each test case, output one line with a string. If there exists a coloring scheme that is not boring, output YES, otherwise output NO.

Any output format that matches one of the formats in the samples or the statement is accepted, i.e. it is case-insensitive. For example, if the standard answer is YES, then YES/Yes/yes are all considered correct.

4
2 10 4
2 3 6
1 4 7
1 1 2

No
Yes
Yes
Yes

8
370359350 416913505 3
761592061 153246036 6
262185277 924417743 5
668232501 586472717 2
891054824 169842323 6
629603359 397927152 2
2614104 175031972 68
924509243 421614240 4

Yes
Yes
Yes
No
No
No
Yes
Yes

Hint

Constraints for all test points: $1 \leq T \leq 10^6$, $1 \leq p_1, p_2, k \leq 10^9$.

Translated by ChatGPT 5