SP84 SHORTCUT - Shortcut

## 题目背景 Mirek从家到大学有很多种走法，但他有一条最喜欢的路径，他每天都走这条路去上学 该路线由许多段组成，每段是一条10米长的线。 段要么是前一段的直线的延伸，要么垂直于前一段 Mirek每走过一段后，会休息一会儿来欣赏大自然的美。 他走路时不会经过之前走过的地方 昨天MiRek在晚会上熬夜画一张样本图，所以他今天起得很晚。 他知道，除非他改变通常的路线，否则他将错过第一堂课。 他计划走一条捷径，且他希望路线尽可能短 （好吧，我们可以秘密告诉你，他不想准时，他只是想安抚他的良心）。 路线必须是连接MiRek家与学校的水平或垂直线段。 请帮Mirek找到最短的路线。 ## 任务 编写一个程序： 读入Mirek的路线，计算路线上最短的路径，并写出结果。

输入从整数T开始，表示测试数据的个数 对于每个测试数据，输入的第一行包含一个整数n（3

输出的第一行和唯一行包含由单个空格分隔的整数L、B、E和字符D。整数L是最短路径的长度（以10米每段测量）。整数b和e是捷径的数目（我们用连续的整数对格点进行编号，Mirek为0，大学为n）。字符D是捷径的方向。如果存在一个以上的最小长度的捷径，则应该输出在路线上最早开始的一条捷径。如果最小长度的多个捷径在同一个格点开始，则应该输出在区域内结束点最远的捷径。