#include

<

stdio.h

>

#include

<

string

.h

>

#define

M 1010

int

c[M][M];

int

f[M][M];

int

min(

int

a,

int

b,

int

c)

{

int

z

=

(a

<

b)

?

a:b;

if

(z

<

c)

return

z;

else

return

c;

}

int

Max(

int

a ,

int

b)

{

return

a

>

b

?

a:b;

}

void

LCS(

char

aa[],

char

bb[],

int

x,

int

y)

{

int

i,j;

for

(i

=

0

;i

<=

x;i

++

)

c[i][

0

]

=

0

;

for

(j

=

0

;j

<=

y;j

++

)

c[

0

][j]

=

0

;

for

(i

=

1

;i

<=

x;i

++

)

for

(j

=

1

;j

<=

y;j

++

)

{

if

(aa[i

-

1

]

==

bb[j

-

1

]) c[i][j]

=

c[i

-

1

][j

-

1

]

+

1

;

else

c[i][j]

=

Max(c[i][j

-

1

],c[i

-

1

][j]);

}

}

int

main()

{

char

a[M],b[M];

int

L1,L2;

int

t;

int

k

=

0

;

scanf(

"

%d

"

,

&

t);

while

(t

--

)

{

scanf(

"

%s %s

"

,a,b);

L1

=

strlen(a);

L2

=

strlen(b);

LCS(a,b,L1,L2);

int

xx

=

c[L1][L2];

int

ans

=

0

;

int

i,j;

f[

0

][

0

]

=

0

;

for

(i

=

0

;i

<=

L1;i

++

)

f[i][

0

]

=

i;

for

(j

=

0

;j

<=

L2;j

++

)

f[

0

][j]

=

j;

for

(i

=

1

;i

<=

L1;i

++

)

for

(j

=

1

;j

<=

L2;j

++

)

{

if

(a[i

-

1

]

==

b[j

-

1

])

//

转移方程

f[i][j]

=

f[i

-

1

][j

-

1

];

else

f[i][j]

=

min(f[i

-

1

][j

-

1

]

+

1

,f[i

-

1

][j]

+

1

,f[i][j

-

1

]

+

1

);

}

printf(

"

Case %d: LCS=%d EditStep=%d\n

"

,

++

k,xx,f[L1][L2]);

}

return

0

;

}