You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

时空限制

1S/512M

题目描述

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

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

共有 $T$ 组数据。

格式

输入格式

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

对于每组数据：

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

输出格式

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

样例

样例输入 #1

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

样例输出 #1

YES
NO
YES

样例解释 #1

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

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

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

数据规模

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