题目描述

有两个按钮：A 按钮按一次得 a 分，B 按钮按一次得 b 分。

初始分数为 0，求是否存在按恰好 n 次按钮后总得分为 k 的可能性。

共有 T 组数据。

输入格式

第一行包含一个整数 T，表示数据的组数。

对于每组数据：

第一行包含四个整数 a,b,n,k，含义与题目描述相同。

输出格式

对于每组数据，在单独的一行中输出字符串表示答案，如果存在按恰好 n 次按钮后总得分为 k 的可能性输出 YES，否则输出 NO。

3
1 10 4 31
1 10 4 30
10 1 4 40

YES
NO
YES

样例解释

对于第 1 组数据，按 1 次 A 按钮，按 3 次 B 按钮，总得分为 1×1+10×3=31。

对于第 2 组数据，不存在按恰好 4 次按钮后总得分为 30 的可能性。

对于第 3 组数据，按 4 次 A 按钮，总得分为 10×4=40。

数据规模与约定

对于100%的数据 $1\leq T\leq 1000, 1\leq a,b\leq 1000 , 1\leq n\leq1000,1\leq k\leq10^6$