血小板拯救伤口

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

题目描述

叮，奋力敲代码的你受到了来自键盘君的若干伤害！

不怕，血小板们挺身而出拯救你伤口！

你的手指伤口为 $\, n*m \,$ 的格子。初始，血小板小队派出了 $\, a \,$ 位萌萌哒的血小板小哥哥小姐姐们，他们位于其中一个格子中。若一个格子存在血小板，每过 $\, 1 \,$ 秒，经过细胞分裂与移动，相邻的格子也存在血小板。请问经过几秒， $\, n*m \,$ 的格子第一次都存在血小板，隔离空气中可恶的病毒君们。

请注意，同一个格子可以有多个血小板，两个格子相邻代表它们存在公共边或公共点。 $\, a \,$ 位血小板的初始位置由你决定。

输入描述:

第行，输入一个整数，代表有组数据。

接下来行，每行输入三个整数。

输出描述:

输出行，每行输出一个整数，为对应的最短的时间。

示例1

输入

复制

输出

复制

1
3
0

说明

对于第一组数据
 代表格子不存在血小板
 代表格子存在血小板

备注:



建议使用快读，下述代码仅供参考