UCI2009D - Digger Octaves


After many years spent playing Digger, little Ivan realized he was not taking advantage of the octaves. Oops, sorry! Most of you were not born when Digger came to light!

Digger is a Canadian computer game, originally designed for the IBM personal computer, back in 1983. The aim of the game is to collect precious gold and emeralds buried deep in subterranean levels of and old abandoned mine.

We Digger gurus call a set of eight consecutive emeralds an octave. Notice that, by consecutive we mean that we can collect them one after another. Your Digger Mobile is able to move in the four directions: North, South, West and East.

In a simplified Digger version, consisting only of emeralds and empty spaces, you will have to count how many octaves are present for a given map.

Input

Input starts with an integer T, representing the number of test cases (1<=T<=20). Each test case consists of a map, described as follows:

An integer N (1<=N<=8), representing the side length of the square-shaped map. N lines follow, N characters each. A 'X' character represents an emerald, and a '.' represents an empty space.

Output

For each test case print the number of octaves on a single line.

Example

Input:
2
3
XXX
X.X
XXX
3
XXX
XXX
XXX

Output: 1
5

hide comments
Prabakaran: 2011-02-15 14:15:08

how is the answer 5 for the second test case?

piyifan: 2009-09-14 10:34:10

There may be some extra char in the input.
Be Careful!

[Trichromatic] XilinX: 2009-07-02 09:47:55

"Octave" means a set of emeralds (their order doesn't matter).


Added by:Yandry Perez
Date:2009-06-23
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO