Cell Tower is an interesting daily puzzle game, https://www.andrewt.net/puzzles/cell-tower/. Here we consider a simplified version. You are given 8×8 square with one character in each cell and a dictionary. Please divide the square into several parts, so that each part is a connected block and the characters in this connected block (from top to bottom and from left to right) make up a valid word (i.e., appear in the dictionary).

Two cells A,B are called connected pair, if A and B directly share the same side, or there exists another cell C so that both A,C and B,C are connected pairs.

A group of cells is called connected block if any pair of cells in this group are connected pairs and the size of this group is either 3 or 4.

input
1 1 1 1 2 3 3 3
0 4 4 4 2 2 2 3
0 0 5 5 6 6 7 7
0 9 5 5 6 8 7 7
9 9 9 1 6 8 8 8
3 1 1 1 2 2 2 2
4 5 6 0 0 4 4 3
7 8 9 0 0 4 3 3
16
1111
2222
3333
444
0000
5555
6666
7777
8888
9999
111
333
3456
789
3478
569

output
2