Matchsticks and Squares

Time limit1sMemory limit128 MB

Summary

Given a grid of matchsticks drawn with horizontal and vertical line segments, count all squares of any size whose four full sides are present.

Level: Medium6 of 10
Topics: Matrix, Brute force, Implementation
Solved: No attempts yet

Problem

Matchsticks are placed along the lines of a grid on a table. A square is formed when every matchstick needed along its four sides is present. Matchsticks inside the square do not affect whether that square is counted.

Given each matchstick arrangement, count all squares that can be formed.

Input

The input consists of several arrangements.

The first line of each arrangement contains two integers $r$ and $c$ , the number of rows and columns. $(1 \le r,c \le 20)$

Then $2r+1$ lines describing the matchstick arrangement follow. The 1st, 3rd, 5th, ... of these lines have length $c$ ; each character is either a hyphen (-) for a horizontal matchstick or an asterisk (*) for an empty space. The 2nd, 4th, 6th, ... of these lines have length $c+1$ ; each character is either a vertical bar (|) for a vertical matchstick or an asterisk (*) for an empty space.

The input ends with 0 0.

Output

For each arrangement, print one line containing the number of squares $X$ in the format X squares.

Examples1

Example 1

Input

2 3
--*
|||*
*-*
|*||
---
2 2
--
|||
--
|||
--
0 0

Expected output

2 squares
5 squares