SP31755 JAN - Januarius, The Travelling Clairvoyant

一年一度的法师大会即将召开，先知詹努阿里乌斯计划前往参会。他打算坐火车到达会场所在的城市，因为火车之旅既舒适又经济。他希望乘坐一趟直达列车，这趟车途经 **n** 个车站，车站按顺序用整数编号。从编号为 1 的车站出发，目的地是编号为 **n** 的车站，中途经过的站点将按编号顺序依次到达。 詹努阿里乌斯之所以喜欢乘火车，除了能享受沿途风景，最主要的是车票便宜。国家铁路公司规定，出行费用取决于跨越的区间数。若乘坐 **i** 个区间，票价为 **w $ _{i} $** 。显然，行程越长，票价越贵。 当然，可以选择不买票冒险搭乘，但在两个连续车站之间的旅途中可能会突遇查票。不过，作为先知的詹努阿里乌斯提前知道每次查票的具体时间。他不需要购买全程票，只需在查票时间拥有一张合法票便可（起点可以在查票前的任何车站，终点在查票后的任何车站）。 购票有两种方式：可以在车站票房购买，也可以在车上向查票员购买，但有几点限制。如果上车时没有票，必须在开车后立刻找到查票员购票，查票员只卖从上车点开始的票。另外，如果在有票房的车站上车并从查票员处购票，需要额外支付费用 **d**。 詹努阿里乌斯在旅途中没有时间下车，所以只能在第一个车站的票房购票，或者在任何车站上车并立刻找查票员购票。 请确定一种购票策略，使得在确保每次查票都有有效票的前提下，总花费最低。

第一行输入一个整数 **t**，表示测试用例的数量。接下来是每个测试用例的详述。 每个测试用例的第一行包含三个整数 **n**、**k** 和 **d**，分别表示车站数、查票次数和需要支付的额外费用（1

对于每个测试用例，输出使总费用最小的购票策略。策略描述以两个整数 **s** 和 **b** 开头，分别表示总费用和购票数（1