贪吃蛇是一款经典电子游戏，被现代艺术博物馆（MoMA）收藏，并被列为史上“百大电子游戏”之一。游戏的目标是移动蛇头吃到苹果。一旦蛇吃到苹果，它就会吃掉苹果并增长。随后会放置一个新的苹果，长大的蛇必须接着去吃掉它。

游戏在一个网格上进行，蛇身的每一节占据一个单元格。蛇头可以向三个方向转弯，但不能后退。蛇身跟随蛇头移动。蛇头不能与蛇身碰撞，也不能离开网格。由于整条蛇是同时移动的，蛇头允许进入蛇尾即将离开的单元格。

玩这个游戏需要敏捷和远见。在蛇身变长时，很容易做出导致蛇头陷入绝境的转弯，使其在到达苹果之前撞到墙壁或自己的身体。

你需要编写一个程序，判断蛇头是否能从当前位置到达苹果，还是说蛇注定会死亡。

输入格式

第一行包含两个整数 $r$ 和 $c$ ($1 \le r, c \le 10, r \cdot c \ge 2$)，表示网格有 $r$ 行 $c$ 列。

接下来的 $r$ 行，每行包含一个长度恰好为 $c$ 的字符串，字符集为： $\{'.', '0', \dots, '9', 'a', \dots, 'f', 'A'\}$

其中 '.' 表示网格中的空单元格，十六进制数字 '0', ..., '9' 和 'a', ..., 'f' 表示蛇，'A' 表示苹果。蛇的长度可以在 1 到 16 个字符之间，'0' 为蛇头，后面紧跟其他十六进制数字，顺序严格（'1' 跟在 '0' 后面，'2' 跟在 '1' 后面，以此类推，中间没有跳过的数字）。保证每个数字最多出现一次，每个数字（'0' 除外）都与前一个数字相邻，且网格中恰好有一个苹果。

输出格式

输出一个整数，如果蛇能到达苹果则输出 1，如果不能到达且注定死亡则输出 0。

Google 版本的贪吃蛇

样例

样例输入 1

5 8
......01
....98.2
...A.7.3
.....654
........

样例输出 1

1

样例输入 2

5 4
...A
....
6789
5432
..01

样例输出 2

0

样例输入 3

5 5
....A
.....
678..
54321
....0

样例输出 3

1

样例输入 4

4 4
567A
4389
12ba
0dc.

样例输出 4

1