堡堡正在一块无穷大的二维平面上散步。对于平面上每个满足 和 均是整数的点 ，都有一条双向小径连接点 和 ，还有另一条双向小径连接点 和 。另外，还有 条额外的双向小径，其中第 条连接点 和 。
堡堡只能沿着小径移动。令 表示堡堡从点 出发到达点 最少需要经过几条小径。给定两个整数 和 ，计算
有多组测试数据。第一行输入一个整数 表示测试数据组数。对于每组测试数据：
第一行输入三个整数 ， 和 （，）。它们的含义如上所述。
对于接下来的 行，第 行输入两个整数 和 （）表示第 条额外小径连接点 和 。保证对于所有 有 或 。
保证所有数据 之和不超过 。请注意， 与 之和没有限制。
每组数据输出一行一个整数表示答案。
2 3 2 4 1 1 0 2 0 0 1 100 100 1000 1000
34 1020100
