Holes

Interview

Time limit1sMemory limit1024 MB

Summary

Count the connected sections of empty cells in a walled grid, and the total number of empty cells.

Level: Easy3 of 10
Topics: Matrix, BFS, DFS
Solved: No attempts yet

Problem

After receiving an impenetrable box, you wonder what's inside! Write a program that finds out how many different disconnected sections the box has, and the total area of the space within the box.

Input

The first line contains a single integer n, the number of data sets that follow. Each data set starts with two integers r and c, the number of rows and columns of the box. The next r lines show the box, with # for walls and . for spaces. The box is surrounded entirely by walls.

Output

Print the number of disconnected sections and the total number of spaces in the box, in the format 2 sections, 9 spaces. Use the singular forms 1 section, 1 space when the count is one.

Examples1

Example 1

Input

2
4 8
########
#...#..#
#.#.#..#
########
3 3
###
#.#
###

Expected output

2 sections, 9 spaces
1 section, 1 space