There is a recently discovered ancient temple, and Daring Do is already exploring it. She's come across an old Artifact of Power, which just seems to be spouting meaningless numbers. "...82980644837721883829806448..."

Reading the inscription on the wall, it gives an explanation to the artifact:

WE HAVE TAPPED INTO THE UNIVERSAL LIFE FORCE.

WE HEAR THE CLOCK TICKING TOWARD THE END.

CAN YOU HEAR IT?

WHEN THE PROPHESIED NUMBERS ARE SAID THE FORETOLD NUMBER OF TIMES

IT ENDS.

Daring Do doesn't know the prophesied numbers or foretold count, so she moves on with exploring.

She gets more clues while exploring:

• The artifact began counting at the beginning of time, starting from 0 and going up 1 step at a time, saying each digit individually. So when it first began, it went "0123456789101112131415...". Each second, it says the next digit. This means at time t=0, it said "0", at time t=1, it said "1", etc.
• The universe will end not on the tick after the prophesied number is said for the final time, it ends on the tick that the prophesied number begins. For instance, if the prophesied numbers were "01", and the foretold number of times were "2", then the universe would end at time t = 11. See below for more examples.
• She's found different things which could be the prophesied numbers, or the foretold number of times, but she's not sure.

Please help her figure out the life time of the universe, if the given pair of a 'foretold count' and 'prophesied numbers' were the true ones. But, if you take too long, the world might end before you figure it out!

Input Description

The first line is an integer T, indicating the number of test cases to follow. The following T lines will contain 2 things: a number K, the foretold count, and a string composed of digits, TARGET.

Output Description

For each test case, please determine S, the number of seconds until the prophesied number would be said for the final time. For test case i, please output "Case #i: S" on an individual line.

Example

Input:
6
1 0
1 00
9 1
2 01
100 25
5555 178

Output:
Case #1: 0
Case #2: 191
Case #3: 22
Case #4: 11
Case #5: 9018
Case #6: 5104196

Explanation of Case #3

The artifact starts "01234567891011121314151617..." We see that '1' occurs for the 9th time at time t = 22.

Limits

For one test file, T ~= 100000. For the other five files, T ~= 10000

Of the possibilities found by Daring Do, they all seem to follow this limit:

LEN(K) + LEN(TARGET) <= 17.

In other words, if TARGET = "1", then K could potentially be "9999999999999999", but no larger.

whereas if TARGET = "1234567890123456", then K could potentially be "9", but no larger.