E. Limousine Rally
time limit per test
4 s
memory limit per test
512 megabytes
input
standard input
output
standard output

You've got a new electronic handheld game "Limousine Rally", and you are so excited! In the game, you drive a car towards the finish while going around the obstacles. The road is represented by a grid $$$n$$$ rows long and $$$m$$$ columns wide. Each cell of the grid is either a normal part of the road or an obstacle.

The rows of the grid are numbered from $$$1$$$ to $$$n$$$ and the columns are numbered from $$$1$$$ to $$$m$$$. The cell in the $$$x$$$-th row and the $$$y$$$-th column is denoted $$$(x, y)$$$. The car has a length of $$$k$$$ cells and at the start of the game it occupies $$$k$$$ consecutive cells from $$$(1, 1)$$$ to $$$(k, 1)$$$.

The game is played in moves. Assuming that the car occupies cells from $$$(x, y)$$$ to $$$(x + k - 1, y)$$$ at the start of the move, you can perform one of the following actions:

  • if $$$y \gt 1$$$, shift the car left, so it will occupy cells from $$$(x, y - 1)$$$ to $$$(x + k - 1, y - 1)$$$;
  • if $$$y \lt m$$$, shift the car right, so it will occupy cells from $$$(x, y + 1)$$$ to $$$(x + k - 1, y + 1)$$$;
  • if $$$x + k - 1 \lt n$$$, advance the car forward, so it will occupy cells from $$$(x + 1, y)$$$ to $$$(x + k, y)$$$.

A move is valid only if none of the cells the car is going to occupy contains an obstacle. The car can not rotate, i. e. it is always aligned vertically. The cells initially occupied by the car do not contain obstacles.

What is the maximum row the car can reach from the starting position using only valid moves? A row is reached if a cell of the car is located in that row. There is no limit on the number of moves.

Input

The first line contains one integer $$$t$$$ ($$$1 \le t \le 5000$$$) — the number of test cases.

The first line of each test case contains three integers $$$n$$$, $$$m$$$, and $$$k$$$ ($$$1 \le n, m \le 10^6$$$; $$$1 \le n \cdot m \le 10^6$$$; $$$1 \le k \le n$$$) — the number of rows and columns in the grid, and the length of the car.

The $$$i$$$-th of the next $$$n$$$ lines contains $$$m$$$ characters '.' and/or 'x' — the description of the $$$i$$$-th row. A '.' denotes a normal part of the road, and an 'x' denotes an obstacle.

Additional constraint of the input: the sum of $$$n \cdot m$$$ over all test cases does not exceed $$$10^6$$$.

Output

For each test case, print a single integer — the maximum row the car can reach.

Example
Input
3
3 2 2
..
..
xx
4 5 2
.x...
.....
...x.
xxxx.
5 4 1
.x.x
....
xxx.
....
.xxx
Output
2
3
5