The world is in turmoil, undead zombies are roaming the Earth, and there's no time for a fancy legend. You are in charge of planning where to develop a human stronghold to fight back against the zombies.

You know there are ~5~ essential things humanity needs to establish a stronghold: food, water, ammunition, building supplies, and a power source. For simplicity, we will assign a letter from A to E to represent each of these essentials, in that order. Since it's well known that the world is square and flat, you can view it as a 2 dimensional grid of ~N~ rows of ~N~ cells each. Each cell may be empty, or it may contain one of the essentials for a stronghold.

The human stronghold should be located in an axis-aligned sub-grid of the original grid that contains at least one of each of the five essentials. How many ways can you choose a sub-grid such that all of the five essentials appear at least once in it?

Input Specification

The first line of input will contain ~N~.
The next ~N~ lines of input will contain ~N~ characters each, each one either an uppercase letter from A to E or a period (.). Letters represent that the cell contains one of the five essentials that is represented by the letter, and a period represents that none of the five essentials is present in that cell.

Output Specification

Output the number of ways to choose a sub-grid for the human stronghold.

Constraints

For all subtasks:

~1 \le N \le 1\,000~

Subtask 1 [15%]

~1 \le N \le 20~

Subtask 2 [15%]

Each of the five essentials will appear only once in the grid.

Subtask 3 [70%]

No additional constraints.

Sample Input

4
.A.E
..D.
.CB.
E..A

Sample Output

6