1909: 兔子跳跃

兔子常常感到孤独，所以当他们决定出去走走，去见见他们的朋友，他们跳的很快。

Iris正走在一条无限长的直线道路上。这条道路上点的编号...，-3，-2，-1，0，1，2，3，...从西到东。Iris的家是在0点上，而她想要见的朋友在点1000000001。她是兔子当然只能通过移动跳跃前行，她有两个跳跃类型：小跳和大跳。当她在点x，通过一小跳，她可以移动到点（x + 2）或（x - 2）。通过一个大跳跃，她可以移动到点（x + largeJump）或点（x - largeJump）。

不幸的是，道路总是那么坑坑洼洼，洞的大小不一，有些还可能包含连续几个点，Iris不能跳到这些洞中。

Iris喜欢用小跳，因为这样更加的省力。请问到达1000000001所要使用的最少的大跳跃数量。如果不能达到这一点，输出-1。

注意，道路无限长，当然能跳到超过1000000001的点。

有多组测试数据：
第一行，包含一个整数Num，表示测试数据的个数。（1<=Num<=10）
每组测试数据，
第一行一个整数N，表示共有N个洞。1<=N<=25.
接下来一行N*2个整数，每个洞的两个端点编号，所有端点都是严格递增顺序给出。[1 and 1,000,000,000]。

最后一个整数largeJump[3 and 1,000,000,000]。

共Num行，
到达目标所需最少大跳跃的次数。无法到达输出-1

5
1
1 2
3
1
1 2
4
1
2 3
3
4
2 17 21 36 40 55 59 74
19
12
187640193 187640493 187640738 187640845 564588641 564588679   
564588696 564588907 605671187 605671278 605671288 605671386   
755723729 755723774 755723880 755723920 795077469 795077625   
795077851 795078039 945654724 945654815 945655107 945655323
475

1
-1
3
5
9