Description

Given two sets of positive integers $\{a,a+1,\cdots,b\}$ and $\{c,c+1,\cdots,d\}$, determine whether $c \cdot (c+1)\cdots d$ is divisible by $a \cdot (a+1)\cdots b$.

Input Format

The first line contains an integer $t$, which indicates the number of test cases.

In the next $t$ lines, four integers $a_i,b_i,c_i,d_i$ are given.

Output Format

Output $t$ lines in total. For the $i$-th line, if $c_i \cdot (c_i+1)\cdots d_i$ is divisible by $a_i \cdot (a_i+1)\cdots b_i$, output DA; otherwise, output NE.

2
9 10 3 6
2 5 7 9

DA
NE

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

DA
NE
DA
DA
DA
DA

Hint

Explanation for Sample 1

According to the statement, multiplying the numbers gives $9 \times 10=90$ and $3 \times 4 \times 5 \times 6=360$. Since $90$ is divisible by $360$, output DA.

We get $2 \times 3 \times 4 \times 5=120$ and $7 \times 8 \times 9=504$. Since $120$ is not divisible by $504$, output NE.

Constraints and Specifications

This problem does not use bundled evaluation. You can get the corresponding score by passing the corresponding subtasks, but there are several constraints.

For $100\%$ of the testdata, $1 \le t \le 10$, $1 \le a_i \le b_i \le 10^7$, $1 \le c_i \le d_i \le 10^7$.

Notes

The score of this problem follows the original COCI settings, with a full score of $70$.

Translated from COCI2020-2021 CONTEST #4 T2 Vepar.

Translated by ChatGPT 5