Description

For any integer sequence, we can insert either the symbol + or - between every two integers to form an expression, and thus compute its value. For a given integer sequence, we can construct different expressions in this way and obtain different values. If any one of these values is divisible by $k$, we say the sequence is divisible by $k$. Your task is to determine whether a given sequence is divisible by a given number.

Input Format

This problem has multiple test cases.

The first line contains an integer $M$, the number of test cases.

For each test case:

• The first line contains two integers $n$ and $k$, where $n$ is the number of integers in the sequence.
• The second line contains $n$ integers, which form the input sequence $\{a_i\}$.

Output Format

Output $M$ lines, each corresponding to a test case in the input. If the sequence is divisible by $k$, output Divisible; otherwise, output Not divisible. There should be no leading or trailing spaces on the line.

2
4 7
17 5 -21 15
4 5
17 5 -21 15

Divisible
Not divisible

Hint

Explanation for Sample 1

For the integer sequence $17, 5, -21, 15$, we can construct $8$ expressions:

• $17+5+(-21)+15=16$.
• $17+5+(-21)-15=-14$.
• $17+5-(-21)+15=58$.
• $17+5-(-21)-15=28$.
• $17-5+(-21)+15=6$.
• $17-5+(-21)-15=-24$.
• $17-5-(-21)+15=48$.
• $17-5-(-21)-15=18$.

This sequence is divisible by $7$ ($17+5+(-21)-15=-14$), but not divisible by $5$.

Constraints For all test points, it is guaranteed that $1 \le M \le 20$, $1 \le n \le 10^4$, $2 \le k \le 100$, and $\left| a_i \right| \le 10^4$.

• $\text{upd 2022.9.27}$: Added one Hack testdata set.
• $\text{upd 2023.11.29}$: Added one Hack testdata set.

Translated by ChatGPT 5