# Looney Tunes

**Problem Statement**

Bugs Bunny is on straight road which is infinitely long. The points on this road are numbered as ...,-4,-3,-2,-1,0,1,2,3,4,5,.. from south to north. Bugs Bunny is at the point 0 now and he is going to meet Daffy Duck who is at the point 1,000,000,001. Bugs Bunny only moves by hopping and he can perform two types of hop: big hop and small hop. If Bugs Bunny is at the point x,

- By making a small hop, he can either move to (x+2) or (x-2)
- By making a big hop, he can either move to (x+bigHop) or (x-bigHop)

Unfortunately Elmer Fudd, the archenemy of Bugs Bunny wants to trap Bugs and puts traps on the road. Bugs Bunny can never get out if he lands on a point containing a trap. You are given an array of integers traps[] having N * 2 elements. For each i (0 <= i < N) , all the points between traps[2 * i] and traps[2 * i + 1], inclusive, contain traps.

Bugs Bunny prefers to do small hops because it is easier and faster. Find the minimum number of big hops required to reach Daffy Duck.

**Input Specification**

The first line of input contains T, the number of test cases.

For each test case, the first line contains N. The second line contains (2*N) elements of traps[]. The last line contains an integer giving the value of bigHop.

Each testcase is separated by a blank line.

**Output Specification**

For each test case, output the minimum number of big hops required to reach Daffy Duck. If it's not possible to reach Daffy Duck, the output should be -1.

**Constraints**

- 1 <= N <= 25
- 1 <= trap[i] <= 1,000,000,000 for all i
- trap[] is in strictly increasing order
- 3 <= bigHop <= 1,000,000,000

**Sample Input**

```
```

5

1

1 2

3

1

1 2

4

1

2 3

3

2

4 5 6 10

7

9

101557142 210995878 245344736 257981537 314968406 363946193 424279117 435779304 441820162 498117144 507089544 553226276 612496883 675096026 730940846 819627580 861535050 862716271

123866101

**Sample Output**

```
```

1

-1

3

-1

9

**Explanation**

```
```

Case #1:

trap[]={1, 2}

bigHop=3

Path: 0,3,5,7,9,.....999999997,999999999,1000000001

No. of big hops made is 1

Case #2: Bugs Bunny can never reach any odd-numbered point.

Case #3:

trap[]={2,3}

bigHop=3

Path: 0, -2, 1, 4, 7, 9, 11,....999999997,999999999, 1000000001

No. of big hops made is 3

*Problem Setter : Rohan Laishram*

**Languages:**C,C++,Java