III. Reading Comprehension (In this section, you are going to read a short passage. Afterwards, you should write a program to answer the sole and only question. Remember that every word in the short passage matters!)

In this problem, you are given an n × m map consisting of '.' and '#', where '.' and '#' represent water and land, respectively. The first and the last rows, and the first and the last columns are called the border, and the border is guaranteed to be water. Water can flow in up, down, left and right, four directions, and water cannot flow into the lands. Similarly, two lands are connected if they share a common edge, i.e., one land appears above, below, on the left side, or on the right side of another land. If land A is connected with land B, and land B is connected with land C, then land A is connected with land C. Furthermore, we can say land A, land B, and land C are all connected. Connected lands form an island.

It is possible that some water cannot flow to the border, i.e., the water is trapped by the island(s). The islands that trap any water form the surroundings. The following map shows an example [Example 1]. The water in the center is trapped by the surroundings.

[Example 1]
........
..####..
.#....#.
.#.##.#.
.#....#.
..####..
........

There are people living in the islands. These people can only travel to the other islands in the water. Consequently, people in some islands can never go to the border directly, since the water near the islands may all be trapped. In [Example 1], people in the island in the center is trapped by the surroundings, i.e., they have to go to the trapped water first, and then to the land of the surroundings, and finally, leave for the border. We call the islands in the trapped water trapped as well. The surroundings, the trapped water, and the trapped island(s) (if there are any), together form a country. In [Example 1], there is one country. And, in [Example 2], there are three countries.

[Example 2]
.........................
..####.....####....####..
.#....#...#....#..#....#.
.#.##.##.##.##.#..#....#.
.#....#...#....#..#....#.
..####.....####....####..
.........................

Let the coordinates of two lands be (x₁, y₁), (x₂, y₂). The Manhattan distance between them is |x₁ - x₂| + |y₁ - y₂|, where |x| is the absolute value of x. If the Manhattan distance between ANY PIECE OF LAND from one country and ANY PIECE OF LAND from another country is no greater than k, these two countries will form an alliance. Analogously, if country A is in alliance with country B, and country B is in alliance with country C, then country A is also in alliance with country C. And, we can say country A, country B, and country C form one alliance. In [Example 2], if k = 2, there are two alliances. If k = 3, there is only one alliance.

Since we are going to be counting, we need to avoid some possible ambiguities:

• Two surroundings are considered to be different if and only if they do not share any common islands. In [Example 3], there are two parts where water is trapped. However, there is only one surroundings -- two parts share the common island in the center. So, there is only one country in [Example 3].

  [Example 3]
  ..........
  ..##..##..
  .#..##..#.
  .#..##..#.
  ..##..##..
  ..........
  

• Any islands that are neither trapped nor being parts of any surroundings are countries. In [Example 4], there are 4 islands and each of them is a country, i.e., there are 4 countries in [Example 4].

  [Example 4]
  .........
  ..#####..
  .#.....#.
  .##..##..
  .........
  

  Why are there 4??? Look at the explanation below.

  (1)       (2)
  #####     #
  
  (3)       (4)
  #         ##
  ##        
  

Now, given k, you are going to tell us the number of alliances in the given map.

HINT: In the last Sample Input, there is only one country. So there is only one alliance.