一头牛站在无限平面上的整点 $(x_0, y_0)$ 处。草生长在一个圆心为整点 $(x_c, y_c)$、半径为整数 $r$ 的圆盘内，以及圆盘的边界上。

牛可以执行任意次数的以下指令：从当前整点 $(x_1, y_1)$ 移动到整点 $(x_2, y_2)$。执行该指令所需的时间等于两点之间的欧几里得距离。这两个点可以重合。

请找到一个指令序列，使牛以最短的时间到达一个有草的整点。

输入格式

第一行包含一个整数 $t$，表示测试用例的数量 ($1 \le t \le 100$)。接下来的 $t$ 行，每行包含一个测试用例。每个测试用例由五个整数 $x_c, y_c, r, x_0, y_0$ 定义：草地圆盘的圆心坐标、半径以及牛的初始坐标 ($-10^9 \le x_c, y_c, x_0, y_0 \le 10^9$, $1 \le r \le 10^9$)。

输出格式

对于每个测试用例，输出两行。第一行输出一个整数 $k$，表示指令的数量 ($0 \le k \le 1\,000\,000$)。第二行输出 $2(k + 1)$ 个整数，表示牛的路径：$x_0 \ y_0 \ \dots \ x_k \ y_k$。如果存在多个最优序列，输出其中任意一个即可。

样例

输入 1

3
1 2 1 1 2
3 2 5 -10 3
0 0 1 10 0

输出 1

0
1 2
1
-10 3 -2 2
3
10 0 5 0 5 0 1 0

说明

图片对应第二个测试用例。

图片对应第二个测试用例。