Migrated from Lutece 1505 Doodle Jump

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

给你四个数,a,n,p,h，其中gcd(a,p)=1,现在你有0,a,2a,3a,4a,...,na，把这n+1个数模p之后排序之后，问两两之间差值是不是都小于等于h，如果是输出YES，否则输出NO

Input

第一行给出一个整数T，表示数据组数
接下来T行，每行四个整数表示a,n,p,h

Output

对于每一组数据，输出一行，YES或者NO

Samples

3
7 4 12 2
7 1 9 4
7 4 12 3

NO
NO
YES

Note

10%的数据 $T=1$
10%的数据 $n=100000$
100%的数据 $T\le10000,1\le a\le 10^9,1\le n<p\le 10^9,0\le h\le 10^9$