Please read the problem statement carefully. Mathematical notations and bunch of examples are provided to make the statement friendly.

Once upon a time, there lived a frog named Joey. He has a long pond beside his house. There are lots of lily pads there, and he likes to jump from one pad to another. He hates to wet himself. Let’s help Joey to cross the pond. For the sake of simplicity, let’s assume the pond to be a line segment of length L. On this line segment there are n lily pads. Let’s enumerate the lily pads from left to right, that is the leftmost pad is number 1, second one from the left is number 2 and so on. At the beginning Joey is at the left end of the pond. Then he moves to the first pad, then to the second pad and so on. At the end he moves from the nth pad to the right end of the pond. There are two ways he can move, jump and swim. He can jump from one place to another if the distance between these two places is no more than D unit. He can swim any times he wants. But as we already said he does not like to wet himself, so we need to minimize the number of times he swims for going from the left end to the right end.

However, the situation is not that simple. There are ropes between every two adjacent places. That is, there is rope between:

• Left end and first pad.
• Last pad and right end.
• Between every two adjacent pads.

Let,

• P_i be the i’th pad (1 <= i <= n), P₀ be the left end and P_n+1 be the right end.
• R_i be the length of the rope R_i between P_i and P_i+1 (for 0 <= i <= n).
• P_i be the position of P_i (0 <= i <= n + 1). Obviously P₀ = 0, P_n+1 = L and P_i < P_i+1, R_i >= P_i+1 - P_i (for 0 <= i <= n).

When Joey is on P_i he can pull R_i and then P_i+1 moves towards Joey. If the rope R_i+1 is taut (the length of the rope is equal to the distance between the two pads that the rope is tied with) then this also affects P_i+2 and P_i+2 moves toward him as well (and so on). However, if a rope is not taut then it does not affect later pads. Also if the ropes are taut till P_n+1 then there is no movements of the pads at all (since the right end is fixed, that is P_n+1 is not movable). Let’s try to clarify these statements by some examples.

Example 1

Let Joey be on P₂, P₂ = 10, P₃ = 20, P₄ = 30, P₅ = 40. Also R₂ = R₃ = R₄ = 15. Distance between P₂-P₃, P₃-P₄ and P₄-P₅ are 10, but the rope lengths are 15. So none of the ropes are taut. Now if Joey pulls R₂ say by 1 unit, P₃ will shift one unit towards P₂ (new P₃ = 19). But this does not affect P₄, because R₃ was not taut. Let Joey pulls rope R₂ 4 more units (5 units in total). Then P₃ = 15, P₄ = 30, P₅ = 40. Now R₃ becomes taut since P₃-P₄ distance is now: P₄ - P₃ = 30 - 15 = 15 which is same as R₃. So now, if Joey pulls one more unit, P₃ and P₄ moves together (P₅ does not, since R₄ is not taut). So the new positions would be: P₃ = 14, P₄ = 29, P₅ = 40.

Example 2

Let Joey be on P₀ and n = 1. Position of the only lily pad P₁ is at P₁ = 10. Let pond length L = 20. By definition P₀ = 0 and P₂ = L = 20. Also let’s assume R₀ = 10, R₁ = 11. If Joey pulls R₀ by one unit then: P₁ = 9. But now R₁ is taut. If he pulls R₀ more P₁ will not move, because the rope between P₁ and P₂ is taut and P₂ is the right end.

Given all the information, you have to figure out minimum number of times Joey has to wet himself in order to go from the left end to the right end. Please note Joey has to move from one place to the next place (he can’t move backward), so he can’t just wet himself once and swim from the left end to the right end.

Input

First line of the input will be a positive integer T (<= 50), number of test cases. Test cases are separated by blank lines. Each case consists of 3 lines. First line contains two positive integers n (<= 1,000) and D (<= 10^9). Second line contains n + 2 integers: P₀, P₁ ... P_n+1. Third line contains n + 1 positive integers R₀, R₁ ... R_n. None of the P_i and R_i will be more than 10^9. You may assume that all of these given values will satisfy all the constraints in the statement. Please note there may be one or more spaces/new lines separating adjacent lines/numbers.

Output

For each of the tests print the case number and the answer.

Example

Input:
5
1 10
0 10 20
10 10

1 10
0 11 20
11 10

1 10
0 11 20
11 9

1 5
0 10 20
20 20

1 5
0 10 20
20 12

Output:
Case 1: 0
Case 2: 0
Case 3: 1
Case 4: 1
Case 5: 2