Given a prime number $p$ and three integers $a, b, c$, you need to perform operations on an integer $x$, which is initially $0$. Each operation can be one of the following two types:

• First type: Update $x$ to $(x \times a) \bmod p$.
• Second type: Update $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 integer number of operations. If it is possible, output Yes; otherwise, output No.

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

Input

This problem contains multiple test cases.

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

Each test case consists of a single line containing four integers $p, a, b, c$.

Output

For each test case, output a single line:

• If it is possible to obtain $c$ after a positive integer number of operations, output Yes.
• If it is not possible to obtain $c$ after a positive integer number of operations, output No.

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

Examples

Input 1

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

Output 1

Yes
Yes
No

Note 1

For the first test case, one can perform the second operation once, followed by the first operation twice.

For the second test case, one can perform the second operation once, followed by the first operation once.

For the third test case, it can be proven that it is impossible to obtain $3$ regardless of the operations performed.

Constraints

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