Problem Description

Given a prime number $p$ and three integers $a, b, c$, you need to perform operations on an integer $x$ that is initially $0$. In each operation, you may choose one of the following two types:

• Type 1 operation: set $x$ to $(x \times a) \bmod p$.
• Type 2 operation: set $x$ to $(x + b) \bmod p$.

Here, $\bmod$ denotes the modulo operation.

You need to determine whether it is possible to obtain $c$ after a positive number of operations. If possible, output Yes, otherwise output No.

In this problem, the output is case-insensitive. That is, yes, yeS, yEs, Yes, YEs, YeS, yES, Yes are all considered Yes, and similarly for No.

Input Format

This problem contains multiple test cases.

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

Then for each test case, one line contains four integers $p, a, b, c$.

Output Format

For each test case, output one line:

• If $c$ can be obtained after a positive number of operations, output Yes.
• Otherwise, output No.

In this problem, the output is case-insensitive. That is, yes, yeS, yEs, Yes, YEs, YeS, yES, Yes are all considered Yes, and similarly for No.

3
5 2 1 4
3 2 2 1
7 2 0 3

Yes
Yes
No

Hint

"Sample Explanation #1"

For the $1$st test case, perform the Type 2 operation once and then perform the Type 1 operation twice.

For the $2$nd test case, perform the Type 2 operation once and then perform the Type 1 operation once.

For the $3$rd test case, it can be proven that no matter how you operate, you cannot obtain $3$.

"Constraints"

For all test cases, $1 \le T \le 100$, $0 \le a, b, c < p \le 10^9$. It is guaranteed that $p$ is prime.

You can get the score for this problem only if you pass all test points.

Translated by ChatGPT 5