Nuts for nuts

Input

The first line of each test case contains the dimensions of the rectangular island $x$ and $y$ (x, y \leq 20). Then follow $x$ lines, each containing $y$ characters, describing the map. The map consists of the symbols $.$, #, and $L$. Initially, Larry and Ryan are at $L$, and the nuts are marked by #; empty cells are marked by $.$. In one step, the boys can move to any of the $8$ adjacent cells. There are at most $15$ cells with nuts. The map contains exactly one cell marked $L$.

Output

For each map, print on a separate line the minimum number of steps required to start at $L$, collect all the nuts, and return to $L$.

Examples