P1089

GC转移

GC转移

撞啊撞,撞啊撞,DP 终于在规定时间内撞完了所有的石头。轰的一声,一扇厚重的石门升起,露出一个门。大家激动地冲了进去,却发现里面是另外一个巨大的迷宫……

又经过 NN 轮天翻地覆的巨响之后,DP 终究还是把头撞昏了。幸好,他撞完了最后一个迷宫。在 DP 昏厥之际,也正是谜题解开之时。最后的一个小石洞里,记录着这里 NN 光年前的历史。

原来在那个时候,也发生过一次巨大的变动。当时的 KD 同样是为了维护世界和平而战死沙场。后来,它的朋友们十分悼念它,其中一部分人开始研究自然法术。经过漫长岁月,复活圣地终于问世,可惜 KD 的残骸早已不知所踪。

由于自然的力量过于强大,研究者不得不将这种力量封印在地底。经历天地轮回之后,他们希望在需要时能够再次将其召唤出来,避免悲剧重演。

当大家得知存在复活圣地时,都既惊讶又兴奋,立即将 KD 和其他阵亡战士的 GC 抬出地面。此时地面早已发生了翻天覆地的变化,战争后破败的土地已经不复存在,只能看见由光构成的网格状平台覆盖着地面,圣地中心清晰可见。

然而,自然的力量实在过于强大,根本无法依靠生物做功将盒子送到中心。爱因斯坦理论空前乏力,牛顿力学也受到了极大的挑战。难道只能依靠说明中介绍的控制地来操纵自然力量、转移盒子吗?可是控制地是什么,又在哪里?大家一脸茫然。

与此同时,临时组成的寻找 F 小队还在墓地内四处搜索,却一无所获。地面裂开时,F 已经落入了墓地下层的地下水系。此时,F 被水流冲上了岸,碰巧来到了传说中的控制地。

F 醒来后,发现四周死寂一片,只能朝唯一的光源靠近。光源处除了一个奇怪的控制器以外什么都没有。别无选择,F 只能一头雾水地按照控制地的说明进行操作,希望找到回到地面的方法。

以 KD 盒子所在的格子为中心,控制地的投光屏上建立了平面直角坐标系,圣地中心的坐标为 (X,Y)(X,Y)。现在的任务是使用各种咒语,将 KD 的盒子移动到圣地中心。

由于控制器年代久远,说明上的文字已经被自然磨损,F 现在能够看清的只有 X 咒语和十字咒语。

每念一次咒语,可以选择某个坐标格作为中心,扩展出一个长度为 LL 的 X 形状或十字形状,并将其顺时针或逆时针旋转 90∘90^\circ。其中,每个格子上的物体都会随之旋转。详细操作如图所示:红色格子为中心,四个方向扩展出的格子数与中心格子一起构成长度,箭头表示物品的转移路径。

为了尽快完成任务并找到回到地面的方法,F 想知道至少需要念多少次咒语才能完成任务。但他似乎数不清自己的蹄子,只好向过去世界的你求助。

输入格式

第一行包含一个正整数 TT,表示需要计算的坐标及长度共有 TT 组。

接下来 TT 行,每行包含三个整数 XX、YY、LL,表示圣地中心的坐标为 (X,Y)(X,Y),咒语中扩展出的 X 形状或十字形状的长度为 LL。咒语不可能白念,因此 L>1L>1。

输出格式

对于每组数据,输出一个整数 ANSANS,表示至少需要念 ANSANS 次咒语才能完成任务。

如果无法完成任务,请输出 Poor F!。

样例输入

3
12 20 5
14 22 5
0 1 2

样例输出

4
5
Poor F!

数据范围

  • 对于 10%10\% 的数据,∣X∣,∣Y∣,∣L∣≤102|X|,|Y|,|L|\le 10^2,T≤5T\le 5;
  • 对于 40%40\% 的数据,∣X∣,∣Y∣,∣L∣≤1016|X|,|Y|,|L|\le 10^{16},T≤100T\le 100;
  • 对于 100%100\% 的数据,∣X∣,∣Y∣,∣L∣≤10500|X|,|Y|,|L|\le 10^{500},T≤1000T\le 1000;
  • 每个数都没有前导 00。

来源与许可

本题题面与测试数据整理自 BZOJ。

样例 1

输入

3
12 20 5
14 22 5
0 1 2

输出

4
5
Poor F!