题目描述

给定两组正整数 $\{a,a+1,\cdots,b\}$ 和 $\{c,c+1,\cdots,d\}$。判断 $c \cdot (c+1)\cdots d$ 能否被 $a \cdot (a+1)\cdots b$ 整除。

输入格式

第一行输入一个整数 $t$，表示数据组数。

接下来的 $t$ 行，输入四个整数 $a_i,b_i,c_i,d_i$。

输出格式

输出共 $t$ 行。对于第 $i$ 行，如果 $c_i \cdot (c_i+1)\cdots d_i$ 能够被 $a_i \cdot (a_i+1)\cdots b_i$ 整除，就输出 DA，否则输出 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

提示

样例 1 解释

按照题意分别相乘得到 $9 \times 10=90$ 和 $3 \times 4 \times 5 \times 6=360$。由于 $90$ 能被 $360$ 整除，因此输出 DA。

我们得到 $2 \times 3 \times 4 \times 5=120$ 和 $7 \times 8 \times 9=504$。而 $120$ 不能被 $504$ 整除，因此输出 NE。

数据规模与约定

本题不采用捆绑评测，通过对应测试点就可以拿到对应的分数，但有若干个约束。

对于 $100\%$ 的数据，$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$。

说明

本题分值按 COCI 原题设置，满分 $70$。

题目译自 COCI2020-2021 CONTEST #4 T2 Vepar。