题目描述

给定四个正整数 $a,b,c,k$，回答是否存在一个正整数 $n$，使得 $k$ 进制下 $a\times n$ 的数位和模 $b$ 为 $c$。

输入格式

第一行一个整数 $T(T \leq 5,000)$。

接下来 $T$ 行，每行四个正整数 $a,b,c,k$ 表示一个询问，所有输入都是十进制的。

输出格式

对于每组数据输出一行一个单词。

Yes表示存在，No​表示不存在。

样例

input

2
3 9 5 10
7 3 1 10

output

No
Yes

数据范围与提示

$1 \leq a \leq 10^{18}, 2 \leq k \leq 10^{18}, 0 \leq c < b \leq 10^{18}​$