DIVCHK - Divisibility Check

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

Added by:Setu
Date:2014-10-10
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64

hide comments
2020-06-09 19:47:11
using Biginteger
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.