该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

说明

给定一个 $n \times m$ 的迷宫，迷宫中有一个固定位置的出口 $T$，入口位置未定，同时迷宫中有些地方是空地，可以穿越，有些地方是障碍，必须绕行，每次从迷宫的一个位置，只能走到与它相邻的 $4$ 个位置中，当然在行走过程中，不能走到迷宫外面去。

现在徐老师有 $Q$ 次询问，每次询问会告诉你一个入口 $S$ 的位置，你需要计算出每个 $S$ 走到 $T$  的最短距离。

输入格式

第一行三个正整数 $n,m,Q$，表示迷宫的大小和询问的次数。

接下来 $n$ 行，每行 $m$ 个字符，其中字符'.'表示该位置为空地，字符'*'表示该位置为障碍，字符'T'表示该位置为迷宫的出口，输入数据中只有这三种字符。

接下来 $Q$ 行，每行两个正整数 $(x_i,y_i)$，表示第 $i$ 次询问起点 $S$ 在 $(x_i,y_i)$ 处，如果起点为 `'*'`则输出 -1。

对于 $20\%$ 的数据，$1\leq n, m \leq 20,q=1$。

对于另外 $20\%$ 的数据，$1\leq n, m \leq 20,1\leq q\leq 10$。

对于另外 $20\%$ 的数据，$1\leq n, m \leq 1000,q=1$。

对于另外 $20\%$ 的数据，$1\leq n, m \leq 1000,1\leq q\leq 10$。

对于 $100\%$ 的数据，$1\leq n, m \leq 1000,1\leq q\leq 10^5$。

输出格式

输出共 $Q$ 行，每行一个整数，第 $i$ 行的输出表示第 $i$ 次询问中 $S$ 到 $T$ 的最短距离，如果不能到达，则输出 $-1$。

样例

6 5 3
.*.*.
.*...
..**.
.....
.*..*
....T
1 1
2 3
4 5

9
8
4