Vepar

Time limit1.5sMemory limit512 MB

Summary

For each test case, decide whether the product of all integers from c to d is divisible by the product of all integers from a to b.

Level: Medium7 of 10
Topics: Number theory, Math, Combinatorics, Prefix sum
Solved: No attempts yet

Problem

Two intervals of positive integers $\{a, a + 1, \ldots, b\}$ and $\{c, c + 1, \ldots, d\}$ are given. Determine whether the product $c \cdot (c+1) \cdots d$ is divisible by the product $a \cdot (a+1) \cdots b$ .

Input

The first line contains a single integer $t$ , the number of independent test cases. ( $1 \le t \le 10$ )

Each of the following $t$ lines contains four positive integers $a_i, b_i, c_i, d_i$ . ( $1 \le a_i \le b_i \le 10^7$ , $1 \le c_i \le d_i \le 10^7$ )

Output

Output $t$ lines in total. For the $i$ -th test case, output DA if $a_i \cdot (a_i + 1) \cdots b_i$ divides $c_i \cdot (c_i + 1) \cdots d_i$ , and output NE otherwise.

Hint

We have $9 \cdot 10 = 90$ and $3 \cdot 4 \cdot 5 \cdot 6 = 360$ . The answer is DA because 90 divides 360.

We calculate $2 \cdot 3 \cdot 4 \cdot 5 = 120$ , which does not divide $7 \cdot 8 \cdot 9 = 504$ . Thus the second answer is NE.

Examples2

Example 1
Input
```
2
9 10 3 6
2 5 7 9
```
Expected output
```
DA
NE
```

Example 2

Input

6
1 2 3 4
1 4 2 3
2 3 1 4
1 3 2 4
19 22 55 57
55 57 19 22

Expected output

DA
NE
DA
DA
DA
DA