Koasar and PGCD#12431
Sign in

Koasar and PGCD

2 seconds
256 megabytes
Medium

You are given three integers , , and . Consider an arithmetic sequence a_1, a_2, \ldots, a_m where:

Your task is to determine whether there exists a positive integer such that the GCD of every pair of distinct elements among the first terms is exactly . In other words: (use O(log^4) gcd algorithm , this is important)

\gcd(a_i, a_j) = g \quad \text{for all } 1 \le i < j \le m

Input

The first line contains a single integer (1 \le t \le 10^4) — the number of test cases.

(use O(log^4) gcd algorithm , this is important)

Each test case consists of a single line containing three integers , , and (1 \le a, g, m \le 10^9)

Output

For each test case, output "YES" if such an integer exists; otherwise, output "NO".

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

Examples

Example 1

Loading
Loading

Note

In the first test case, a = 6, g = 2, m = 3.

  • Choose d = 2: the sequence is [6, 8, 10].

  • \gcd(6, 8) = 2, \gcd(6, 10) = 2, \gcd(8, 10) = 2.

  • All pairwise GCDs equal g = 2, so the answer is YES.

In the second test case, a = 6, g = 3, m = 3. No valid d > 0 exists, so the answer is NO.

Scoring

  1. Subtask ( points) : No additional constraints.