给定两个正整数区间 $\{a, a + 1, \dots, b\}$ 和 $\{c, c + 1, \dots, d\}$。

判断乘积 $c \cdot (c+1) \cdots d$ 是否能被乘积 $a \cdot (a+1) \cdots b$ 整除。

输入格式

第一行包含一个整数 $t$ ($1 \le t \le 10$)，表示独立测试用例的数量。

接下来的 $t$ 行，每行包含四个正整数 $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$)。

输出格式

输出共 $t$ 行。对于第 $i$ 个测试用例，如果 $a_i \cdot (a_i + 1) \cdots b_i$ 能整除 $c_i \cdot (c_i + 1) \cdots d_i$，则输出 DA（克罗地亚语中的“是”），否则输出 NE（克罗地亚语中的“否”）。

子任务

• 在值 10 分的测试数据中，满足 $a_i, b_i, c_i, d_i \le 50$。
• 在另外值 20 分的测试数据中，满足 $a_i, b_i, c_i, d_i \le 1000$。
• 在另外值 10 分的测试数据中，满足 $a_i = 1$。

样例

输入样例 1

2
9 10 3 6
2 5 7 9

输出样例 1

DA
NE

输入样例 2

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

输出样例 2

DA
NE
DA
DA
DA
DA

说明

第一个样例解释：

对于第一个测试用例，我们有 $9 \cdot 10 = 90$ 且 $3 \cdot 4 \cdot 5 \cdot 6 = 360$。因为 $90$ 能整除 $360$，所以答案是 DA。

对于第二个测试用例，我们计算 $2 \cdot 3 \cdot 4 \cdot 5 = 120$，它不能整除 $7 \cdot 8 \cdot 9 = 504$。因此答案是 NE。