Katniss 处于一条非常长的直隧道中，并想要逃离这里。她可以沿着隧道双向移动。隧道中恰好有一个舱门，如果她到达舱门，就可以逃离。

不幸的是，事情并没有那么简单。在 $n$ 个位置有格栅阻挡了整个隧道的宽度。这些格栅是锁着的，Katniss 在解锁格栅之前无法通过它。幸运的是，在隧道沿线的 $n$ 个点上放有 $n$ 把钥匙。每个格栅都可以被这 $n$ 把钥匙中的恰好一把解锁。一旦格栅被解锁，Katniss 就可以自由且重复地通过它。她可以捡起并携带无限数量的钥匙。

Katniss 知道她自己的位置，以及所有 $n$ 把钥匙、所有 $n$ 个格栅和舱门的位置。她也知道哪把钥匙可以解锁哪个格栅。请确定她为了逃离必须移动的最短距离。

输入格式

每个测试点包含多个测试用例。第一行包含测试用例的数量 $t$ ($1 \le t \le 5 \cdot 10^4$)。接下来是测试用例的描述。

每个测试用例的第一行包含三个整数 $n$、$s$ 和 $h$，分别表示格栅的数量、Katniss 的初始坐标以及舱门的坐标 ($1 \le n \le 2 \cdot 10^5$；$-10^6 \le s, h \le 10^6$)。

接下来的 $n$ 行中，第 $i$ 行包含两个整数 $k_i$ 和 $g_i$，分别表示第 $i$ 把钥匙的坐标以及可以用这把钥匙解锁的格栅的坐标 ($-10^6 \le k_i, g_i \le 10^6$)。

所有 $2n + 2$ 个整数 $s, h, k_i$ 和 $g_i$ 两两不同。

保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

输出格式

对于每个测试用例，输出 Katniss 逃离路线的最小可能长度。如果无法逃离，则输出 $-1$。

样例

输入样例 1

3
5 5 13
3 7
8 14
-1 11
9 1
2 10
4 40 0
20 80
50 30
70 60
90 10
1 -1 6
11 8

输出样例 1

32
-1
7

说明

在第一个测试用例中，其中一条最短的逃离路线如下： $5$（初始位置）$\to 3$（捡起钥匙 1）$\to 7$（解锁格栅 1）$\to 9$（捡起钥匙 4）$\to 1$（解锁格栅 4）$\to -1$（捡起钥匙 3）$\to 2$（捡起钥匙 5）$\to 10$（解锁格栅 5）$\to 11$（解锁格栅 3）$\to 13$（舱门）。