PAINTWAL - Paint on a Wall

no tags 

Annie wants to paint her wall to an expected pattern. The wall can be represented as a 2*n grid and each grid will be painted only one color. Annie has a brush which could paint a rectangular area of the wall at a single step. The paint could be overlap and the newly painted color will replace the older one.

For a given pattern of the wall, your task is to help Annie find out the minimum possible number of painting steps. You can assume that the wall remains unpainted until Annie paint some colors on it.

Input

There are multiple test cases in the input. The first line contains the number of test cases.

For each test case, the first line contains the only integer n indicating the length of the wall. (1 <= n <= 8)

Two lines follow, denoting the expected pattern of the wall. The color is represented by a single capital letter.

See the sample input for further details.

Output

For each test case, output only one integer denoting the minimum number of steps.

Example

Input:
3
3
ABA
CBC
3
BAA
CCB
3
BBB
BAB

Output:
Case #1: 3
Case #2: 3
Case #3: 2
The time limit is somewhat tight for this problem.

hide comments
:D: 2013-03-13 22:18:12

"The time limit is somewhat tight for this problem."

No, it isn't :)


Added by:Fudan University Problem Setters
Date:2011-09-08
Time limit:3s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Fudan University Local Contest #3, by g201513