미로

몇 푼이라도 벌기 위해 당신은 과학 실험에 참가하기로 했습니다. 실험에서는 피자를 잔뜩 먹은 뒤, 오직 피자의 힘만으로 움직이는 스쿠터를 타고 도시를 가로질러 목적지까지 가야 합니다.

도시는 격자 모양의 교차로로 이루어져 있고, 각 교차로마다 이동 규칙이 정해져 있습니다. 지도의 각 칸은 다음 네 가지 기호 중 하나로 표시됩니다.

• + : 이 칸에서 동, 서, 남, 북 어느 방향으로든 나갈 수 있습니다.
• - : 이 칸에서는 동쪽 또는 서쪽으로만 나갈 수 있습니다.
• | : 이 칸에서는 북쪽 또는 남쪽으로만 나갈 수 있습니다.
• * : 이 칸에는 들어갈 수 없습니다.

각 기호는 그 칸을 떠날 때 이동할 수 있는 방향을 나타냅니다. 도시의 북서쪽 끝(맨 왼쪽 위 칸)에서 출발하여 남동쪽 끝(맨 오른쪽 아래 칸)까지 이동할 때, 지나야 하는 교차로의 최소 개수를 구하세요. 이때 출발 칸과 도착 칸도 함께 셉니다.

첫째 줄에 테스트 케이스의 수 $t$ ($1 \le t \le 10$) 가 주어집니다.

각 테스트 케이스는 한 줄에 행의 수 $r$, 그다음 줄에 열의 수 $c$ ($1 \le r, c \le 20$) 가 주어집니다. 이어서 $r$개의 줄에 각각 $c$개의 문자가 주어지며, 각 문자는 +, -, |, * 중 하나입니다. 북서쪽 끝 칸은 항상 들어갈 수 있음이 보장됩니다(즉 *가 아닙니다).

각 테스트 케이스마다 한 줄에 정수 하나를 출력합니다. $i$번째 줄에는 $i$번째 테스트 케이스에서 북서쪽 끝에서 남동쪽 끝까지 이동할 때 지나야 하는 교차로의 최소 개수를 출력합니다. 북서쪽 끝에서 남동쪽 끝까지 갈 수 없다면 그 테스트 케이스에는 $-1$을 출력합니다.