Prof. Ossama's budget

Interview

Time limit1sMemory limit256 MB

Summary

Each test case asks for the remainder when a fund N with up to one million digits is divided by X.

Level: Easy3 of 10
Topics: Math, String
Solved: No attempts yet

Problem

Prof. Ossama Ismail directs the ACPC regional contest. One year he decided to plan the budget like this. Every team receives the same amount $A$ , and $A$ is taken as large as possible, so the fund is split into equal shares until less than one team's share is left. Whatever remains after that goes to the other needs of the contest.

Fund raising went well that year, so $N$ can have a great many digits. Given the fund $N$ and the number of teams $X$ , find how much money is left for the other needs.

Input

The first line contains an integer $T$ , the number of test cases ( $1 \le T \le 100$ ).

Each of the next $T$ lines contains two integers $N$ and $X$ separated by a space. $N$ is the available fund, a positive integer with no leading zeros and at most one million digits. $X$ is the number of teams ( $1 \le X \le 10^7$ ).

Output

For each test case print one line in the form Case n: R, where $n$ is the test case number starting from $1$ and $R$ is the money left for the other needs of the contest.

Examples7

Example 1
Input
```
2
10 3
500 220
```
Expected output
```
Case 1: 1
Case 2: 60
```
Example 2
Input
```
1
7 100
```
Expected output
```
Case 1: 7
```

Example 3

Input

3
1 1
9999999999999999999999999 1
5 1

Expected output

Case 1: 0
Case 2: 0
Case 3: 0

Example 4

Input

4
1 10000000
9 10000000
10000000 10000000
9999999 10000000

Expected output

Case 1: 1
Case 2: 9
Case 3: 0
Case 4: 9999999

Example 5

Input

3
111111111111111111111111111111111111111111111111111111111111 3
111111111111111111111111111111111111111111111111111111111111 9
111111111111111111111111111111111111111111111111111111111111 11

Expected output

Case 1: 0
Case 2: 6
Case 3: 0

Example 6

Input

5
100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 7
100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 9973
100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 1000000
100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 9999999
100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 2

Expected output

Case 1: 2
Case 2: 8340
Case 3: 0
Case 4: 10000
Case 5: 0

Example 7

Input

6
99999999999999999 9999991
999999999999999999 9999991
9999999999999999999 9999991
99999999999999999999999999999999999 9999991
999999999999999999999999999999999999 9999991
9999999999999999999999999999999999999 9999991

Expected output

Case 1: 80999
Case 2: 809999
Case 3: 8099999
Case 4: 59048
Case 5: 590489
Case 6: 5904899