Dice

Interview

Time limit2sMemory limit1024 MB

Summary

Given n dice with f faces and a modifier m, decide whether a reported total S is reachable by checking if S minus m lies between n and n times f.

Level: Easy2 of 10
Topics: Math, Implementation
Solved: No attempts yet

Problem

Khodislav is playing a tabletop role-playing game. He has finally chosen his weapons to deal with a monster and casts the crushing strike. To do this, he rolls dice, adds up the numbers on their faces, and announces the sum to the game master.

A group of identical dice rolls is defined by three integers $n$ , $f$ , and $m$ . Here $n$ is the number of dice, $f$ is the number of faces on each die, and $m$ is the modifier. Each face shows every number from $1$ to $f$ , any face can come up, and all rolls are independent. For example, if $n = 3$ , $f = 8$ , and $m = 5$ , the player rolls three eight-sided dice, adds the results, and then adds $5$ . This is usually written as $3d8 + 5$ .

The game master wants to check whether the sum Khodislav reported can actually be obtained from the roll.

Input

The first line contains a single integer $B$ ( $1 \le B \le 10^5$ ), the number of strikes cast by Khodislav. Each of the following $B$ lines describes one strike with four integers: the reported sum $S$ , followed by $n$ , $f$ , and $m$ . The constraints are $1 \le S \le 300$ , $1 \le n \le 10$ , $2 \le f \le 20$ , and $0 \le m \le 10$ .

Output

For each strike, in the same order as the input, print YES if the reported sum is achievable, and NO otherwise. Print each answer on its own line.

Examples1

Example 1

Input

Expected output

YES
NO
NO
NO
YES