*Again
Prime? No time.***Input:** standard input**Output:** standard output**Time
Limit:** 1 second

* n* you have to
determine the largest power of

__Input__

The input file consists of several test
cases. The first line in the file is the number of cases to handle. The
following lines are the cases each of which contains two integers * m
(1<m<5000)* and

For each case in the input, print the case number and result in separate lines.
The result is either an integer if * m* divides

__Sample
Input__

2

2 10

2 100

__Sample Output__

Case 1:

8

Case 2:

97

Problem setter: Anupam Bhattacharjee, CSE, BUET

`Thanks to Shabuj for checking and Adrian for alternate solution.`

"**~~
Algorithms are the rhythms of Computer Science ~~**"