You are given a grid, find the longest path in it. The grid is filled with '#' which means blocked cell and '.' which means an empty cell. A path is a chain of empty cells that each cell is neighbor with the next one. Each cell is a neighbor with cells that share a side with it. A cell cannot appear twice in the path.

Input format

• The first line contains $n$.
• The next $n$ lines contain the grid.

Output format

In the first line, print $k$ denoting the length of the path.

In the next $k$ lines, print the cells in order.

Constraints

$1 \le n \le 1000$

Test generation

At the first, a random number $prob$ is generated in range (0, 1). Then each cell becomes '#' with probability $prob$.