Large Division (大数求余）

Given two integers, a and b, you should check whether a is divisible by b or not. We know that an integer a is divisible by an integer b if and only if there exists an integer c such that a = b * c.

Input

Input starts with an integer T (≤ 525), denoting the number of test cases.

Each case starts with a line containing two integers a (-10 ≤ a ≤ 10) and b (|b| > 0, b fits into a 32 bit signed integer). Numbers will not contain leading zeroes.

Output

For each case, print the case number first. Then print 'divisible' if a is divisible by b. Otherwise print 'not divisible'.

Sample Input

6

101 101

0 67

-101 101

7678123668327637674887634 101

11010000000000000000 256

-202202202202000202202202 -101

Sample Output

Case 1: divisible

Case 2: divisible

Case 3: divisible

Case 4: not divisible

Case 5: divisible

Case 6: divisible

#include <iostream>

#include <algorithm>

#include <cstring>

#include <cstdio>

#include <vector>

#include <iomanip>

#include <cmath>

#include <ctime>

#include <map>

#include <set>

using namespace std;

#define lowbit(x) (x&(-x))

#define max(x,y) (x>y?x:y)

#define min(x,y) (x<y?x:y)

#define MAX 100000000000000000

#define MOD 1000000007

#define pi acos(-1.0)

#define ei exp(1)

#define PI 3.141592653589793238462

#define INF 0x3f3f3f3f3f

#define mem(a) (memset(a,0,sizeof(a)))

typedef long long ll;

char a[];

ll b,t,ans;

int main()

{

    scanf("%d",&t);

    int k=t;

    while(t--)

    {

        scanf("%s %lld",a,&b);

        b=abs(b);

        printf("Case %d: ",k-t);

        ans=;

        for(int i=;i<strlen(a);i++)

        {

            if(a[i]=='-') continue;

            ans=ans*+(a[i]-'');

            ans=ans%b;

            if(ans==) {puts("divisible");goto end;}

        }

        puts("not divisible");

        end:;

    }

    return ;

}