Amr M. believes in conspiracies. He is very suspicious about everything, and he is always trying to uncover the truth to everyone (or so he thinks). Lately he became very suspicious of TV ads, especially the ones that are made of 2 words: ad1 and ad2, and thinks they carry hidden messages.

After contacting his top secret resources, he found out the process that the evil people use to hide the message. The original message is always two strings: orig1 and orig2.

The transformation happened as follows:

1. The letters from orig1 are shuffled.
2. The letters from orig2 are shuffled.
3. One letter from either orig1 or orig2 is replaced with its next or previous letter in the alphabet.

This produces ad1 and ad2 from orig1 and orig2 respectively. For example for orig1 = "bcd", orig2 = "wcy" we may have ad1 = "dcb", ad2 = "cxy" (shuffled to cwy and 'w' replaced with 'x'.)

After more research, Amr also found out the distance X, which is equal to distance(orig1, ad1) + distance (orig2, ad2). The distance between 2 strings is the sum of absolute difference between the letters at same positions (e.g. difference("ab", "cd") = abs('a'-'c') + abs('b'-'d') = 4)

But the number of possible original messages appears to be very high, so Amr hired you to count them. Given string ad1 and ad2, and X = distance(orig1, ad1) + distance (orig2, ad2), return the number of possible strings orig1 and orig2.

Input

The first line of input contains an integer T that represents the number of test cases, then follow T lines each line is in format ad1 ad2 X, space separated where ad1, ad2 are composed from English lowercase letters.

1 ≤ length (ad1), length(ad2) ≤ 10, 'b' ≤ ad1[i], ad2[i] ≤ 'y' and 0 ≤ X ≤ 100000

Output

For each test case, output a single line of output in the form “Case K: cnt” where K is the number of the test case and cnt is the number of possible strings orig1 and orig2.

Example

Input:
2
c n 1
kbenh kbenh 5

Output:
Case 1: 4
Case 2: 16