题目描述

给定一个质数 $p$ 和三个整数 $a,b,c$，你需要对一个初始为 $0$ 的整数 $x$ 进行操作，每次操作可以进行如下的两种之一：

• 第一种操作：令 $x$ 的值变为 $(x \times a) \bmod p$。
• 第二种操作：令 $x$ 的值变为 $(x+b) \bmod p$。

其中，$\bmod$ 表示取模运算。

你需要求出能否在正整数次操作后得到 $c$，若能则输出 Yes，否则输出 No。

本题中字符串大小写不敏感，即 yes、yeS、yEs、Yes、YEs、YeS、yES、Yes 都被认为是 Yes，No 同理。

输入格式

本题有多组测试数据。

第一行输入一个整数 $T$，表示测试数据组数。

接下来依次输入每组测试数据。对于每组测试数据，输入一行四个整数 $p,a,b,c$。

输出格式

对于每组测试数据，输出一行：

• 若能在正整数次操作后得到 $c$，则输出 Yes；
• 若不能在正整数次操作后得到 $c$，则输出 No。

本题中字符串大小写不敏感，即 yes、yeS、yEs、Yes、YEs、YeS、yES、Yes 都被认为是 Yes，No 同理。

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

Yes
Yes
No

提示

「样例解释 #1」

对于第 $1$ 组数据，进行 $1$ 次第二种操作后进行 $2$ 次第一种操作即可。

对于第 $2$ 组数据，进行 $1$ 次第二种操作后进行 $1$ 次第一种操作即可。

对于第 $3$ 组数据，可以证明无论如何操作都无法得到 $3$。

「数据范围」

对于所有数据，$1\le T \le 100$，$0\le a,b,c < p \le 10^9$，保证 $p$ 是质数。

只有你通过本题的所有测试点，你才能获得本题的分数。