给定四个正整数a,b,c,k，回答是否存在一个正整数n，使得a*n在k进制表示下的各位的数值之和模b为c。

输入描述:

第一行一个整数T(T 接下来T行，每行四个正整数a,b,c,k（1 ≤ a ≤ 10^18; 2 ≤ k ≤ 10^18; 0 ≤ c b ≤ 10^18）表示一个询问，所有输入都是十进制的。

输出描述:

对于每组数据输出一行，Yes表示存在，No表示不存在。