## Problem Description

LCP (Longest Common Prefix), is defined as the longest common prefix of two strings. For example, LCP (“AC”, “ACOrz”) = “AC”, LCP (“WA”,”AC”) = “”.

Now you are given several DNA sequence. (Only contains ‘A’, ‘T’, ‘C’ and ‘G’).

You are expected to output the length of the LCP of two DNA sequence.

## Input

In the first line there is an integer T, indicates the number of test cases. (T <= 10)

In each case, the first line contains only one integer n, indicates the number of DNA sequence. (1 <= n <=100000, the number of letters in one test case is smaller than 100000)

Then one integer m, then m lines, each line contains two integers a,b ,indicates the index of the two DNA sequence. (0 <= m <= 100000, 0<= a,b <n)

## Output

For each case, output “Case idx: “first where idx is the case index start from 1 in a single line , then output m lines indicate the length of the LCP.

## Sample Input

2
2
ATCG
AT
1
0 1
3
AT
ATT
ATTT
3
0 0
0 1
0 2

## Sample Output

Case 1:
2
Case 2:
2
2
2

## Source

FOJ有奖月赛-2010年11月