Amit has come to the Universal Parking Space. He has to go on an inter-galaxy trip and needs to park his car here. The parking lot is made of many unit-spaced parallel lines numbered integers 1 to M. Amit must park his car such that the center of his car passes one of these lines. Amit's car is SIZE units wide, thus even though his center part lies on one line, the car as a whole may be passing over many lines.
He must also ensure that any part of his car does not touch either of the edge lines of the parking lot, i.e., the lines 1 and M (they have very high electromagnetic discharge).

Now, in his galaxy all the cars need to be fitted with radiation withstanding shields as Radiation Missiles can be dropped by the AlphaCentauri invaders anytime. These Radiation Missiles land at one point and spread upto a particular range in exactly one direction(left or right) before it bursts into flames. Bob must also ensure that his car does not touch any of the end points, i.e., where the missile lands and where the missile bursts. However, if his car happens to be between these end points, then it will still be safe if not more than K missile radiations pass through it.

Can you tell Bob the number of lines on which he can safely park his car such that the it is not harmed?

Input:

First line consists of 1 integer T indicating the number of test cases.

First line of each test case contains 4 integers N, M, SIZE and K where :

• N is the number of radiation missiles landing in the parking lot
• M is the number of lines in the parking lot (indexed 1 to M)
• SIZE is the width of Bob's car and
• K is the maximum number of radiation missiles that his car can withstand.

• POS indicates the line where the radiation missile lands and
• RANGE indicates the number of units it moves before it bursts into flames.
• If RANGE is positive, it indicates that the radiation goes RANGE units towards right side.
• If RANGE is negative, it indicates that the radiation goes RANGE units towards left side from the POS.

Output:

For each test case, output the number of possible points where he can park the car without suffering any damage.

Constraints:

• 1 ≤ T ≤ 10
• 0 ≤ N ≤ 10⁵
• 1 ≤ M ≤ 10⁹
• 1 ≤ POS ≤ M
• -M ≤ RANGE ≤ M
• 1 ≤ SIZE ≤ M
• 0 ≤ K ≤ N
• 0 ≤ sum of N over all test cases ≤ 10⁵

Scoring:

• 1 ≤ N ≤ 10, 1 ≤ M ≤ 100 : (30 pts)
• 1 ≤ N ≤ 1000, 1 ≤ M ≤ 10⁵: (30 pts)
• Original Constraints : (40 pts)