Migrated from Lutece 1500 G

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Little Ruins is a studious boy, but in rest time, he will play some little game.

Today he found a game of eliminate: there is $N\times M$ tiles which only contains # and *, you have two patterns to eliminate tiles:

.
..

and

 .
..

Each step you can use a pattern and eliminate tiles on the bottom two lines. After each step,the tiles above eliminated tiles will fall down.

Your goal is to eliminate all * tiles, please calculate the minimum steps.

Input

First line contains an integer $T$ ($1\le T\le 50$), which indicates the number of test cases.

Every test case begins with two integers $N$ and $M$ ($1\le N\le 2000,2\le M\le 2000$), which indicates the size of tiles.

In the following $N$ lines, every line contains $M$ characters means the type of tiles.

For $80\%$ of the use cases, $1\le N,M\le 100$ holds.

Output

For every test case, you should output Case #x: y, where x indicates the case number and counts from $1$ and y is the result.

Samples

1
3 2
#*
*#
##

Case #1: 2

Note

The kinds of tiles which are eliminated in one step can be different.

Resources

第二届中国大学生程序设计竞赛 杭州站（CCPC 2016 Hangzhou Site）