### 问题描述 与美团合作的交大校园专属共享单车为同学们的校园生活提供了不少便利。但是现在出现了一个问题，有少部分同学为了赶时间，使用完单车后并没有把单车停放在规定的停放位置，以至于校园内的共享单车零零散散很不美观，但是这些没有停放在规定位置的单车，数量没有达到需要出动运营货车来统一调度的必要。 为了校庆期间校园的环境美观，安排了数量刚好够的热心校园志愿者，通过搬动共享单车来让它们归位，每个志愿者的任务是归位任意一辆单车即可。很显然，归位一对相距最近的单车和停车位即可迅速完成自己的任务，可是为了集体着想并不能这样做，而且每一个志愿者都想尽快完成这个任务，去排练重要的校庆演出活动。 那么最优做法即是：合理安排谁去归位哪辆共享单车，让最慢完成任务的那个志愿者消耗的时间也尽可能的短。 但是志愿者小Q觉得这个最优做法比较简单，突发奇想的他想知道：假设所有人完成任务的时间加起来的总和为 $S$，$S$ 最小是多少？ 我们将一片矩形的校园区域按坐标系划分成若干个正方形的块形区域，除了围墙和花坛是禁止通行的方块外，其他方块均保证足够通畅（即可同时通过多辆共享单车）**，**另外：一个包含停车位的区域只能停放一辆共享单车，是否已停放单车也并不影响此方块的畅通。假定开始时有 $k$ 名志愿者已经找到了所有零散的 $k$ 辆共享单车，并且假设搬动共享单车时只能前后左右移动，每一步移动都会消耗一单位时间，设某一安排方案下志愿者们将共享单车搬到规定停车位的时间分别为 $T1,T2,\dots ,Tk$，则所有人完成任务的时间总和 $S= T1+T2+\dots +Tk$，请设计程序找出最小的 $S$。 ### 输入格式 第一行输入 $T$，代表样例的数量 $(1\leq T \leq10)$。 第二行输入 $n$ 和 $m$，代表这一片校园区域，区域内有若干辆共享单车（总数不超过 $5$），还有若干个规定停车位（总数不超过 $10$）,$(1\leq n,m \leq 50)$。 接下来输入 $n$ 行 $m$ 列，代表区域内各方块的具体情况，以下是输入的含义： "Q"：围墙，"H"：花坛，"C"：单车，"P"：车位，"."：道路。 （保证答案一定存在，且空闲停车位的数量大于等于单车数量）。 ### 输出格式 输出一个数，代表最小的，所有志愿者完成任务的时间加起来的总和 $S$。 ### 样例输入 ```text 2 2 6 .C..PP .....C 3 9 HQPP.PPQH HQQQ.QQQH CCC..C... ``` ### 样例输出 ```text 4 24 ```