No testdata at current.

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

背景

小X收集够了木头后，准备下矿

题目介绍

由于这是一个无规则服务器，所以小X想要利用透视挖矿，所以他知道所有矿的位置，小X已经有了一把石镐、无限多的木头、熔炉和工作台，小X想先挖3块铁和一块煤炭做铁镐然后尽可能多的挖钻石，小X是个若只大聪明，他想找你帮忙N*M范围内找到他最少要走几格才能收集完所需的铁和煤炭. 在范围里，*为铁矿所在位置，.是石头，X是小X的位置，q是煤矿所在位置，必定有可以收集齐全的方案

输入

第一行依次输入N, M表示在N*M的范围内 以下N行，每行有M个字符，均为* q X

输出

小X收集完所需的铁和煤炭最少走的格数

懒得写

懒得写

Limitation

1<=m, n<=100000