If I ask you: is number 15 divisible by 3? How can you say yes, 15 is divisible 3? I think you will just check, if 15 mod by 3 is 0 then Yes, otherwise No. But if I give you a binary number like 1111 and ask is this binary’s decimal number is divisible by 3? Now its your task to find out the divisibility.

Input

Input file starts with a test case T (1 <= T <= 100) . Each test case follows a binary string which will contain at most 200 bits and a divisibility checking number N (2 <= N <= 5).

Output

If the binary number divisible by N then print “Divisible By N” otherwise “Not Divisible By N”. N means The divisibility checking number N.

Example

Input:
2
1111
3
101
2

Output:
Divisible By 3
Not Divisible By 2