旅行者偷走了芙宁娜最爱的甜点。此时，芙宁娜正在由 行 列方格组成的枫丹国内内四处搜捕他。方格以从上到下 行、从左到右 列编号。初始时刻为 ，旅行者位于左上角格子 ，他的目标是在大门关闭前到达右下角格子 从而逃离枫丹国。旅行者的移动规则如下： 在每一个时刻，他只能沿向下或向右选择一个方向移动，并可以一次前进任意正整数步；移动完成后，时刻加 。 芙宁娜派出了 名检查官，第 名检查官将在时刻 占据格子 并一直驻守。无论旅行者在时刻 ： 到达该格子； 经过该格子； 离开该格子， 他都会立即被捕获，从而导致逃脱失败。此外，在时刻 之后大门将被永久关闭，若旅行者到达 时时刻已经大于 ，则同样逃脱失败。 请你帮助旅行者计算： 在所有合法方案中逃离所需的最短时间； 在模 意义下，可以逃脱的总方案数量。

输入描述:

本题包含多组测试数据。第一行输入一个整数 代表数据组数，每组测试数据描述如下：一行四个整数 ；此后 行，第 行输入三个整数 ――第 名检查官的坐标及出现时刻。此外，数据保证  和  两格不会有检查官出现，但是可能会出现很多检察官出现在同一个格子的情况。

输出描述:

对于每组测试数据：若 Traveler 无论如何都无法逃脱，输出一行-1；否则输出两个整数，依次为 方案数量（对 取模）与 最短时间。