{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"After the great winger Donaldo left his soccer team, coach sir Thelex has found himself in a great fix. The strength of his team is reduced greatly and he needs to find a suitable replacement immediately. The coach selects a number of young wingers from around the world and sets up a trial for them.\n\nThe trial will take place on a rectangular shaped field of length **L** meters and width **W** meters. There are **N** robot defenders placed on the field. The defenders do not change their positions but if a winger\u0027s distance from a defender is not more than **d** meters, it will automatically tackle him. A robot defender may tackle at most once. On the beginning of the trial, a winger stands on the left edge of the field (across the length) with a soccer ball. Now, his task is to avoid the obstructions of the robot defenders and reach the rightmost edge of the field with the ball. Please tell him the minimum number of tackles he must face in order to reach the opposite end. A player must not go outside the field or he will be disqualified."}},{"title":"Input","value":{"format":"MD","content":"Input starts with an integer **T (\u0026le; 100)**, denoting the number of test cases.\n\nEach case starts with a line containing four integers **L W N d (1 \u0026le; L, W \u0026le; 10000, 1 \u0026le; N \u0026le; 100, 1 \u0026le; d \u0026le; 1000)** as described above. Each of the following N lines contains two integers defining the **x** and **y** co-ordinates of a defender. You can consider the co-ordinate of the lower-left corner of the field to be **(0, 0)** and upper-right corner to be **(L, W)**. Obviously, all the defenders are located inside the field. The left edge is denoted by the line **(0, 0), (0, W)** and the right edge is denoted by the line **(L, 0), (L, W)**. The winger wants to move from left edge to right."}},{"title":"Output","value":{"format":"MD","content":"For each case, print the case number and the minimum number of tackles that needs to be dealt with."}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2\n500 300 5 100\n250 0\n250 150\n250 300\n100 150\n400 150\n10 10 4 4\n2 3\n8 3\n2 7\n8 7\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eCase 1: 1\nCase 2: 2\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}