One day, a single mouse gained the ability to teleport. In an attempt to study its true capabilities, a group of scientists do what they know best: place it in a maze and see how quickly it can reach the cheese at the end!

The maze can be represented as a grid with N rows (numbered 1 to N from top to bottom) and M columns (numbered 1 to M from left to right). Each of its cells is either empty or blocked, denoted by . and #, respectively.
The teleporting mouse is placed at cell (1, 1) of the grid, and the cheese at cell (N, M). It is guaranteed that both these cells are not blocked.

The mouse has the following abilities:

• From (x, y), it can move to one of the four adjacent cells: (x-1, y), (x+1, y), (x, y-1), (x, y+1).
  This can be done only if the destination cell lies within the grid and is not blocked.
  This movement is not considered to be a teleport.
• From (x, y), it can also teleport at most K cells in any of the four directions.
  That is, it can move to some cell of the form (x-i, y), (x+i, y), (x, y-i), or (x, y+i) where i <= K, again provided the destination cell is within the grid and not blocked.

Find the minimum number of teleports the mouse needs to reach the cheese.
If the mouse cannot reach the cheese no matter what, print -1 instead.

Input Format

• The first line contains T, the number of test cases. The description of each test follows.
  • The first line of each test contains N, M, and K: the dimensions of the grid and the mouse's teleport distance.
  • The next N lines each contain a string of length M, representing the N x M grid.

Output Format

Print a single integer for each test case: the minimum number of teleports needed by the mouse to reach (N, M).
If it's impossible for the mouse to reach the end, print -1 instead.

Constraints

• 1 <= T <= 100
• 2 <= N, M <= 3000
• 1 <= K <= min(N, M)
• Each cell of the grid is either . or #.

Subtasks

• In 10% of the files, the sum of N and the sum of M within a file both won't exceed 10.
• In another 15% of the files, the sum of N and the sum of M within a file both won't exceed 100.
• In another 25% of the files, the sum of N and the sum of M within a file both won't exceed 1000.
• The remaining 40% of files have no further constraints.

Sample 0

Input

4
6 5 1
.#.#.
#####
#..##
#.##.
###..
..#..
6 5 2
.#.#.
#####
#..##
#.##.
###..
..#..
6 5 3
.#.#.
#####
#..##
#.##.
###..
..#..
6 5 5
.#.#.
#####
#..##
#.##.
###..
..#..

Output

-1
4
3
2

Explanation

All four examples have the same maze.

In the first example, the mouse is unable to move at all.
In the second example, here is one optimal sequence using four teleports:

• (1, 1) -> (1, 3) by teleporting.
• (1, 3) -> (3, 3) by teleporting.
• (3, 3) -> (3, 2) by direct movement.
• (3, 2) -> (4, 2) by direct movement.
• (4, 2) -> (6, 2) by teleporting.
• (6, 2) -> (6, 4) by teleporting.
• (6, 4) -> (6, 5) by direct movement.