跑步
题号：NC220162
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

NIT走到了一片森林，这片森林可以抽象成一个n*m的矩阵。有一些地方长有树，NIT不能走到上面去。NIT可以上下左右或斜向八连通行走。

现在NIT想跑跑步锻炼身体，他想沿着一条路走然后回到起点。并且NIT想这条路径一定是一个至少包着一颗树的环。请问这条路径的最短长度是多少。

输入描述:

第一行有三个整数n,m,q表示森林的长宽以及询问个数
接下来n行,每行m个字符,表示森林的情况。其中”.”表示空地,”X”表示树。
接下来q行每行两个数x，y表示NIT的起点（起点不会是树）保证有合法路径。

输出描述:

输出q行，每行表示每个询问的最短路长度
示例1

输入

复制 
6 7 3
.......
...X.X.
...X.X.
...XXX.
.X.....
.......
1 7
3 7
3 1

输出

复制 
13
12
6

说明

备注:

对于15%的数据，n,m<=3
对于30%的数据，n,m<=8
对于另外30%的数据，保证树林组成的联通块只有一个
对于100%的数据，n,m<=1000,q<=5