D - Decision

08.01.2010
TrudnośćTrudność

Time limit: 2 s
Memory limit: 64 MB

In a galaxy not so far away, in a time where men were real men, women were real women, and small furry creatures from Alpha Centauri were real small furry creatures from Alpha Centauri, an astronom called Mr. Gorsky discovered a small inhabited planet. After an initial enthusiasm (yes, we are not alone!), all the living Nobel Peace Prize winners gathered in one place, formed a committee, and discussed options of invading the planet. Long story short, in order to decide on this important topic, they need to know the number of the cities on the remote planet.

The quality of photos delivered by Mr. Gorsky were unfortunately quite bad: on a rectangular grid, each grid element was either blank (no city there) or (partially) dark, which meant a city or a part of it. If two dark parts share a common edge, they are a part of the same city. The committee then said plainly: ``You have to count the number of the cities. Good luck, Mr. Gorsky''.

An example map containing three cities is presented below.

Multiple Test Cases

The input contains several test cases. The first line of the input contains a positive integer $ Z \leq 20 $, denoting the number of test cases. Then $ Z $ test cases follow, each conforming to the format described in section Single Instance Input. For each test case, your program has to write an output conforming to the format described in section Single Instance Output.

Single Instance Input

The first line of an input instance contains two integers $ n $ and $ m $, the photo dimensions, such that $ 1 \leq n,m \leq 1000 $. The following $ n $ lines contain the description of the photo. Each line contains $ m $ characters from the set $ \{ {\tt A}, {\tt B}, {\tt C},
{\tt D}, {\tt E}, {\tt F} \} $ encoding the grid elements in the following way:

Single Instance Output

For each input instance, your program should output one line containing the number of cities on a given map.

Example

Input

4
1 2
DD
2 2
FB
DF
2 3
FAA
AFB
4 4
AACB
CAFD
AFCE
AACA

Output

2
1
2
6
Nie możesz wysyłać i oglądać rozwiązań tego zadania ponieważ nie jesteś zalogowany. Zaloguj się lub załóż konto.
0
Twoja ocena: Brak

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com