Read problems statements in Mandarin Chinese and Russian as well. 

There are 100 houses located on a straight line. The first house is numbered 1 and the last one is numbered 100. Some M houses out of these 100 are occupied by cops.
Thief Devu has just stolen PeePee's bag and is looking for a house to hide in.
PeePee uses fast 4G Internet and sends the message to all the cops that a thief named Devu has just stolen her bag and ran into some house.
Devu knows that the cops run at a maximum speed of x houses per minute in a straight line and they will search for a maximum of y minutes. Devu wants to know how many houses are safe for him to escape from the cops. Help him in getting this information.

------ Input ------ 

First line contains T, the number of test cases to follow.
First line of each test case contains 3 space separated integers: M, x and y.
For each test case, the second line contains M space separated integers which represent the house numbers where the cops are residing.

------ Output ------ 

For each test case, output a single line containing the number of houses which are safe to hide from cops.

------ Constraints ------ 

$1 ≤ T ≤ 10^{4}$
$1 ≤ x, y, M ≤ 10$

----- Sample Input 1 ------ 
3

4 7 8

12 52 56 8

2 10 2

21 75

2 5 8

10 51
----- Sample Output 1 ------ 
0

18

9
----- explanation 1 ------ 
Test case $1$: Based on the speed, each cop can cover $56$ houses on each side. These houses are:
- Cop in house $12$ can cover houses $1$ to $11$ if he travels left and houses $13$ to $68$ if he travels right. Thus, this cop can cover houses numbered $1$ to $68$.
- Cop in house $52$ can cover houses $1$ to $51$ if he travels left and houses $53$ to $100$ if he travels right. Thus, this cop can cover houses numbered $1$ to $100$.
- Cop in house $56$ can cover houses $1$ to $55$ if he travels left and houses $57$ to $100$ if he travels right. Thus, this cop can cover houses numbered $1$ to $100$.
- Cop in house $8$ can cover houses $1$ to $7$ if he travels left and houses $9$ to $64$ if he travels right. Thus, this cop can cover houses numbered $1$ to $64$.

Thus, there is no house which is not covered by any of the cops.

Test case $2$: Based on the speed, each cop can cover $20$ houses on each side. These houses are:
- Cop in house $21$ can cover houses $1$ to $20$ if he travels left and houses $22$ to $41$ if he travels right. Thus, this cop can cover houses numbered $1$ to $41$.
- Cop in house $75$ can cover houses $55$ to $74$ if he travels left and houses $76$ to $95$ if he travels right. Thus, this cop can cover houses numbered $55$ to $95$.

Thus, the safe houses are house number $42$ to $54$ and $96$ to $100$. There are $18$ safe houses.

Source: codechef | Difficulty: EASY
Tags: Sorting

Complete search


Solutions:
t = int(input())
for i in range(t):
	(m, x, y) = map(int, input().split())
	a = list(map(int, input().split()))
	s = x * y
	h = [i for i in range(1, 101)]
	for i in range(m):
		l = []
		l = [i for i in range(a[i] - s, a[i] + s + 1)]
		h = [i for i in h if i not in l]
	print(len(h))


for _ in range(int(input())):
	(m, x, y) = map(int, input().split())
	p = x * y
	a = list(map(int, input().split()))
	a.sort()
	s = []
	for i in a:
		for j in range(i - p, i + p + 1):
			s.append(j)
	c = 0
	for k in range(1, 101):
		if k not in s:
			c = c + 1
	print(c)


x = int(input())
for v in range(x):
	(m, s, t) = input().split(' ')
	(m, s, t) = map(int, (m, s, t))
	houses = list(map(int, input().split(' ')))
	can = s * t
	t = [i for i in range(1, 101)]
	for k in range(m):
		searched = [i for i in range(houses[k] - can, houses[k] + can + 1)]
		t = [i for i in t if i not in searched]
	print(len(t))


tests = int(input())
for i in range(tests):
	(m, x, y) = map(int, input().split())
	arr = list(map(int, input().split()))
	available_arr = [1 for i in range(101)]
	available_arr[0] = 0
	for j in arr:
		right_house = min(100, j + x * y) + 1
		left_house = max(0, j - x * y) - 1
		for k in range(j, right_house):
			available_arr[k] = 0
		for k in range(j, left_house, -1):
			available_arr[k] = 0
	print(available_arr.count(1))


t = int(input())
for i in range(t):
	(num, speed, time) = map(int, input().split())
	houses = map(int, input().split())
	remaining = set(range(1, 101))
	for cop in houses:
		remaining -= set(range(cop - speed * time, cop + speed * time + 1))
		if not remaining:
			break
	print(len(remaining))


t = int(input())
for i in range(t):
	(m, x, t) = map(int, input().split())
	cops = list(map(int, input().split()))
	a = x * t
	arr = list(bytearray(101))
	for i in range(m):
		l = cops[i] - a
		r = cops[i] + a
		if l <= 0:
			l = 1
		if r >= 100:
			r = 100
		for k in range(l, r + 1):
			arr[k] += 1
	print(arr.count(0) - 1)


for i in range(int(input())):
	(m, x, y) = map(int, input().split())
	l = [int(x) for x in input().split()]
	a = x * y
	s = [i for i in range(1, 101)]
	for i in range(m):
		k = [x for x in range(l[i] - a, l[i] + a + 1)]
		s = [x for x in s if x not in k]
	print(len(s))


for i in range(int(input())):
	(m, x, y) = map(int, input().split())
	l = list(map(int, input().split()))
	l.sort()
	k = []
	j = []
	g = 0
	for i in range(m):
		k.append(l[i] - x * y)
		j.append(l[i] + x * y)
	if k[0] > 0:
		g += k[0] - 1
	if j[-1] < 100:
		g += 100 - j[-1]
	for i in range(m - 1):
		if k[i + 1] - j[i] > 0:
			g += k[i + 1] - j[i] - 1
	print(g)


a = int(input())
for i in range(a):
	l1 = list(map(int, input().split()))
	l2 = list(map(int, input().split()))
	s = l1[1] * l1[2]
	ans = 0
	total = [i for i in range(1, 101)]
	for i in range(l1[0]):
		searched = []
		searched = [i for i in range(l2[i] - s, l2[i] + s + 1)]
		total = [i for i in total if i not in searched]
	print(len(total))


t = int(input())
for _ in range(t):
	(M, x, y) = [int(x) for x in input().split()]
	houses = [int(x) - 1 for x in input().split()]
	mark = [0 for _ in range(100)]
	low = 0
	high = 0
	houses = list(sorted(houses))
	n = x * y
	for h in houses:
		low = max(h - x * y, 0)
		high = min(h + x * y, 99)
		for j in range(low, high + 1):
			mark[j] = 1
	print(100 - sum(mark))


try:
	for _ in range(int(input())):
		(M, x, y) = map(int, input().split())
		m = list(map(int, input().split()))
		c = x * y
		total = [i for i in range(1, 101)]
		for i in range(M):
			s = []
			s = [i for i in range(m[i] - c, m[i] + c + 1)]
			total = [i for i in total if i not in s]
		print(len(total))
except:
	pass


for i in range(int(input())):
	(m, x, y) = map(int, input().split())
	l = list(map(int, input().split()))
	l.sort()
	c = 0
	if l[0] - x * y <= 1:
		c += 0
	elif l[0] - x * y > 1:
		c += l[0] - x * y - 1
	if l[-1] + x * y >= 100:
		c += 0
	elif l[-1] + x * y < 100:
		c += 100 - (l[-1] + x * y)
	for i in range(m - 1):
		if l[i] + x * y < l[i + 1] - x * y:
			c += l[i + 1] - 2 * x * y - l[i] - 1
		else:
			c += 0
	print(c)


for _ in range(int(input())):
	(M, x, y) = map(int, input().split())
	coph = [int(x) - 1 for x in input().split()]
	coph.sort()
	copi = 0
	totali = 0
	trys = 0
	ans = 0
	while copi < M and totali < 100:
		if totali < coph[copi] - x * y:
			ans += 1
			totali += 1
		elif totali > coph[copi] + x * y:
			copi += 1
		else:
			totali += 1
	print(ans + 100 - totali)


for tc in range(int(input())):
	(m, x, y) = map(int, input().split())
	cops = list(map(int, input().split()))
	cops.sort()
	dist = x * y
	(s, e) = (0, 1)
	count = 0
	for i in range(m):
		cops[i] = [cops[i] - dist, cops[i] + dist]
	for ele in cops:
		if ele[0] > s:
			count += ele[0] - s - 1
		s = ele[1]
	if s < 100:
		count += 100 - s
	print(count)


for _ in range(int(input())):
	(m, x, y) = map(int, input().split())
	cphs = list(map(int, input().split()))
	cphs.sort()
	l = []
	sum = 0
	for i in range(m + 1):
		if i == 0:
			l.append(cphs[i] - 1)
		elif i == m:
			l.append(100 - cphs[i - 1])
		else:
			l.append(cphs[i] - cphs[i - 1] - 1)
	for j in range(m + 1):
		if j == 0 and l[j] > x * y:
			sum = sum + (l[j] - x * y)
		elif j == m and l[j] > x * y:
			sum += l[j] - x * y
		elif l[j] > 2 * x * y:
			sum = sum + (l[j] - 2 * x * y)
	print(sum)


for i in range(int(input())):
	l = list(map(int, input().split()))
	x = l[1] * l[2]
	n = list(map(int, input().split()))
	ar = []
	for a in n:
		for b in range(a - x, a + x + 1):
			if b > 0 and b <= 100 and (b not in ar):
				ar.append(b)
	print(100 - len(ar))


def safe_houses(A, B):
	c = []
	safeHouses = 0
	for i in range(len(A)):
		for k in range(A[i], B[i] + 1):
			c.append(k)
	for i in range(1, 101):
		if i not in c:
			safeHouses += 1
	return safeHouses
T = int(input())
for i in range(T):
	(M, x, y) = map(int, input().split())
	arr = list(map(int, input().split()))
	covered = x * y
	leftl = []
	rightl = []
	(left, right) = (0, 0)
	for i in range(len(arr)):
		if arr[i] - covered <= 1:
			left = 1
			leftl.append(left)
		elif arr[i] - covered > 1:
			left = arr[i] - covered
			leftl.append(left)
		if arr[i] + covered >= 100:
			right = 100
			rightl.append(right)
		elif arr[i] + covered < 100:
			right = arr[i] + covered
			rightl.append(right)
	print(safe_houses(leftl, rightl))


h = int(input())
um = []
mty = []
for iie in range(1, 101):
	mty.append(iie)
for ii in range(0, h):
	gb = str(input())
	bv = str(input())
	hjk = []
	pp = gb.split(' ')
	for iit in pp:
		hjk.append(int(iit))
	ty = []
	for tte in bv.split(' '):
		ty.append(int(tte))
	oopt = [hjk, ty]
	um.append(oopt)
for iite in um:
	yew = iite[0][1] * iite[0][2]
	ppoy = iite[1]
	tkr = list(mty)
	for iimr in ppoy:
		yupt = iimr - yew
		if yupt <= 0:
			yupt = 1
		mplt = iimr + yew
		if mplt > 100:
			mplt = 100
		gk = []
		for iiew in tkr:
			if iiew >= yupt and iiew <= mplt:
				continue
			else:
				gk.append(iiew)
		tkr = list(gk)
	print(len(tkr))


for i in range(int(input())):
	l = list(map(int, input().split()))
	l1 = list(map(int, input().split()))
	s = l[1] * l[2]
	total = [i for i in range(1, 101)]
	for j in range(l[0]):
		s1 = []
		s1 = [i for i in range(l1[j] - s, l1[j] + s + 1)]
		total = [i for i in total if i not in s1]
	print(len(total))


for _ in range(int(input())):
	(housecop, rate, search) = map(int, input().split())
	locations = map(int, input().split())
	remaining = set(range(1, 100 + 1))
	for cop in locations:
		remaining -= set(range(cop - rate * search, cop + rate * search + 1))
		if not remaining:
			break
	print(len(remaining))


t = int(input())
for z in range(t):
	(m, x, y) = [int(x) for x in input().split()]
	arr = [int(x) for x in input().split()]
	houses = x * y
	li = []
	for ele in arr:
		if ele - houses > 0:
			cover_left = ele - houses
		else:
			cover_left = 1
		if ele + houses <= 100:
			cover_right = ele + houses
		else:
			cover_right = 100
		li += [i for i in range(cover_left, cover_right + 1)]
		li = list(set(li))
	print(100 - len(li))


for _ in range(int(input())):
	(n, x, y) = list(map(int, input().split()))
	cops = list(map(int, input().split()))
	cops = sorted(cops)
	safe = [1] * 101
	x *= y
	for i in cops:
		if i - x > 0:
			for i in range(i - x, i + x + 1):
				if i > 100:
					break
				safe[i] = 0
		else:
			for i in range(1, i + x + 1):
				if i > 100:
					break
				safe[i] = 0
	print(safe.count(1) - 1)


T = int(input())
for _ in range(T):
	(M, x, y) = [int(x) for x in input().split()]
	H = [int(x) for x in input().split()]
	t = x * y
	H.sort()
	arr = [1] * 100
	for i in H:
		nmin = max(1, i - t)
		nmax = min(i + t, 100)
		for j in range(nmin, nmax + 1):
			arr[j - 1] = 0
	print(sum(arr))


t = int(input())
for _ in range(t):
	(m, x, y) = list(map(int, input().split(' ')))
	ml = x * y
	arr = list(map(int, input().split(' ')))
	houses = [1] * 100
	for i in arr:
		r = i + ml
		r = r if r <= 100 else 100
		l = i - ml
		l = l if l > 1 else 1
		houses[l - 1:r] = [0] * (r - l + 1)
	print(sum(houses))


def main():
	for _ in range(int(input())):
		(m, x, y) = map(int, input().split(' '))
		arr = list(map(int, input().split(' ')))[:m]
		maxCoverArea = x * y
		Total = [i for i in range(1, 101)]
		for x in range(m):
			CoverArea = []
			CoverArea = [i for i in range(arr[x] - maxCoverArea, arr[x] + maxCoverArea + 1)]
			Total = [i for i in Total if i not in CoverArea]
		print(len(Total))
main()


for _ in range(int(input())):
	(x, y, z) = map(int, input().split())
	l = list(map(int, input().split()))
	l.sort()
	c = []
	for i in l:
		for j in range(i - z * y, i + z * y + 1):
			c.append(j)
	d = []
	for t in range(1, 101):
		if t not in c:
			d.append(t)
	print(len(d))


T = int(input())
for i in range(T):
	integer = list(map(int, input().split()))
	house_covered = integer[1] * integer[2]
	house = list(map(int, input().split()))
	arr = []
	for a in house:
		for b in range(a - house_covered, a + house_covered + 1):
			if b > 0 and b <= 100 and (b not in arr):
				arr.append(b)
	print(100 - len(arr))


t = int(input())
for i in range(t):
	p = list(map(int, input().strip().split(' ')))
	m = list(map(int, input().strip().split(' ')))
	a = []
	houses = p[1] * p[2]
	for i in m:
		x = i + houses
		y = i - houses
		if y < 0:
			y = 1
		if x > 100:
			x = 100
		z = [j for j in range(y, x + 1)]
		for k in z:
			if k not in a:
				a.append(k)
	c = 0
	for i in range(1, 101):
		if i not in a:
			c += 1
	print(c)


tc = int(input())
for _ in range(tc):
	(M, x, y) = map(int, input().split())
	a = list(map(int, input().split()))
	dist = x * y
	houses = 100
	for i in range(1, 101):
		max_dist = i + dist
		min_dist = i - dist
		if min_dist < 1:
			min_dist = 1
		if max_dist > 100:
			max_dist = 100
		for j in range(min_dist, max_dist + 1):
			if j in a:
				houses -= 1
				break
	print(houses)


for _ in range(int(input())):
	(m, x, y) = map(int, input().split())
	cops_pos = list(map(int, input().split()))
	n = x * y
	notsafe = []
	arr = [i for i in range(1, 101)]
	setarr = set(arr)
	for pos in cops_pos:
		notsafe.extend(range(pos - n, pos + n + 1))
	ns = list(set(arr) & set(notsafe))
	if set(arr) - set(ns):
		print(len(set(arr) - set(ns)))
	else:
		print(0)


t = int(input())
for i in range(t):
	q = set()
	(M, x, y) = map(int, input().split())
	v = list(map(int, input().split()))
	for w in v:
		if w <= x * y:
			a = {s for s in range(1, w)}
			b = {s for s in range(w, w + x * y + 1) if s <= 100}
			q = q.union(a)
			q = q.union(b)
		else:
			e = {s for s in range(w - x * y, w)}
			d = {s for s in range(w, w + x * y + 1) if s <= 100}
			q = q.union(d)
			q = q.union(e)
	print(100 - len(q))


for _ in range(int(input())):
	(M, x) = (lambda i: [i[0], i[1] * i[2]])([int(i) for i in input().split()])
	lista = [int(a) for a in input().split()]
	y = set(range(1, 101))
	for i in lista:
		y -= set(range(i - x, i + x + 1))
	print(len(y))


for i in range(int(input())):
	(m, x, y) = map(int, input().split())
	l = list(map(int, input().strip().split(' ')))
	r = x * y
	countlist = []
	for j in range(101):
		countlist.append(0)
	for j in range(m):
		left = l[j] - r
		right = l[j] + r
		if left <= 0:
			left = 1
		if right >= 100:
			right = 100
		for k in range(left, right + 1):
			countlist[k] += 1
	print(countlist.count(0) - 1)


t = int(input())
for i in range(t):
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	s = a[1] * a[2]
	ans = 0
	total = [i for i in range(1, 101)]
	for i in range(a[0]):
		count = []
		count = [i for i in range(b[i] - s, b[i] + s + 1)]
		total = [i for i in total if i not in count]
	print(len(total))


import sys
R = lambda : map(int, next(sys.stdin).split())
T = int(input())
for i in range(T):
	(M, x, y) = R()
	houses = []
	for i in range(100):
		houses.append(0)
	total = x * y
	cops = list(R())
	for i in range(M):
		if cops[i] - total - 1 < 0:
			start = 0
		else:
			start = cops[i] - total - 1
		if cops[i] + total - 1 > 99:
			end = 99
		else:
			end = cops[i] + total - 1
		for j in range(start, end + 1):
			houses[j] = 1
	safe = 0
	for i in range(100):
		if houses[i] == 0:
			safe += 1
	print(safe)


for i in range(int(input())):
	(M, x, y) = map(int, input().split())
	ch = list(map(int, input().split()))
	ch.sort()
	arr = []
	cnt = 0
	for i in range(M):
		l_count = ch[i] - x * y if ch[i] - x * y > 1 else 1
		r_count = ch[i] + x * y if ch[i] + x * y < 100 else 100
		arr.append(l_count)
		arr.append(r_count)
	for i in range(0, len(arr), 2):
		if i == 0:
			cnt += arr[i] - 1
		elif arr[i] > arr[i - 1]:
			cnt += arr[i] - arr[i - 1] - 1
		if i == len(arr) - 2:
			cnt += 100 - arr[i + 1]
	print(cnt)


x = int(input())
for i in range(x):
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	s = a[1] * a[2]
	ans = 0
	total = [i for i in range(1, 101)]
	for i in range(a[0]):
		searched = []
		searched = [i for i in range(b[i] - s, b[i] + s + 1)]
		total = [i for i in total if i not in searched]
	print(len(total))


for _ in range(int(input())):
	(m, x, y) = map(int, input().split())
	l = list(map(int, input().split()))
	ma = x * y
	houses = [i for i in range(1, 101)]
	for i in range(m):
		z = []
		z = [i for i in range(l[i] - ma, l[i] + ma + 1)]
		houses = [i for i in houses if i not in z]
	print(len(houses))


T = int(input())
for _ in range(T):
	(m, x, y) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	c = 0
	x1 = 0
	for i in a:
		if i - x * y <= 1:
			x1 = i + x * y
		elif i - x * y <= x1:
			x1 = i + x * y
		else:
			c += i - x * y - x1 - 1
			x1 = i + x * y
	if x1 < 100:
		c += 100 - x1
	print(c)


t = int(input())
for i in range(t):
	(m, x, y) = map(int, input().split())
	speed = x * y
	l = list(map(int, input().split()))
	s = set()
	for j in range(0, m):
		num1 = l[j] - speed
		for k in range(l[j], num1 - 1, -1):
			if k > 0:
				s.add(k)
		num2 = l[j] + speed
		for k in range(l[j], num2 + 1):
			if k <= 100:
				s.add(k)
	print(100 - len(s))


T = int(input())
for test_case in range(T):
	(M, x, y) = tuple((int(_) for _ in input().split()))
	cops = tuple((int(_) for _ in input().split()))
	remaining_houses = set(range(1, 100 + 1))
	for c in cops:
		remaining_houses -= set(range(c - x * y, c + x * y + 1))
		if not remaining_houses:
			break
	print(len(remaining_houses))


t = int(input())
for tc in range(t):
	(m, x, y) = map(int, input().split())
	s = x * y
	b = []
	l = list(map(int, input().split()))
	for j in l:
		for j in range(j - s, j + s + 1):
			if j > 0 and j <= 100 and (j not in b):
				b.append(j)
	print(100 - len(b))


for i in range(int(input())):
	(M, x, y) = map(int, input().split())
	ch = list(map(int, input().split()))
	arr = [0 for x in range(100)]
	for cop in ch:
		left = cop - x * y if cop - x * y > 1 else 1
		right = cop + x * y if cop + x * y < 100 else 100
		for j in range(left, right + 1):
			arr[j - 1] = 1
	print(arr.count(0))


t = int(input())
res = []
for i in range(t):
	(m, x, y) = map(int, input().split())
	li = list(map(int, input().split()))
	cvrg = x * y
	houses = list(range(1, 101))
	for k in range(m):
		u = min(li[k] + cvrg, 100)
		l = max(1, li[k] - cvrg)
		while l <= u:
			houses[l - 1] = 0
			l += 1
	houses = set(houses)
	res.append(str(len(houses) - 1))
print('\n'.join(res))


try:
	for _ in range(int(input())):
		(M, x, y) = map(int, input().split())
		H = list(map(int, input().split()))
		H.sort()
		R = x * y
		C = 0
		if H[0] - 1 > R:
			C += H[0] - 1 - R
		for i in range(1, len(H)):
			if H[i] - H[i - 1] > 2 * R:
				C += H[i] - H[i - 1] - 2 * R - 1
		if 100 - H[-1] > R:
			C += 100 - H[-1] - R
		print(C)
except:
	pass


n = int(input())
for _ in range(n):
	(m, x, y) = map(int, input().split())
	M = list(map(int, input().split()))
	a = []
	b = 0
	for i in range(m):
		left = M[i] - x * y
		right = M[i] + x * y
		if left <= 0:
			left = 1
		else:
			left = left
		if right > 100:
			right = 100
		else:
			right = right
		for j in range(left, right + 1):
			a.append(j)
	b = len(set(a))
	if b == 100:
		print(0)
	else:
		print(100 - b)


def safe(m, x, y):
	h = x * y
	l = set()
	r = set()
	for i in m:
		if i <= h:
			l = l.union(set(range(1, i)))
			r = r.union(set(range(i + 1, i + h + 1))) if i + h <= 100 else r.union(set(range(i + 1, 101)))
		else:
			l = l.union(set(range(i - h, i)))
			r = r.union(set(range(i + 1, i + h + 1))) if i + h <= 100 else r.union(set(range(i + 1, 101)))
	a = l.union(r).union(set(m))
	res = [x for x in range(1, 101) if x not in a]
	return len(res)
for _ in range(int(input())):
	(a, x, y) = map(int, input().split())
	m = list(map(int, input().split()))
	print(safe(m, x, y))


num = int(input())
for _ in range(num):
	lst1 = list(map(int, input().split()))
	lst2 = list(map(int, input().split()))
	time = lst1[1] * lst1[2]
	arr = []
	lst2.sort()
	for l in lst2:
		a = 1
		b = 100
		if l > time:
			a = l - time
		if l + time < 100:
			b = l + time
		arr.append(a)
		arr.append(b)
	cnt = 0
	for i in range(0, len(arr), 2):
		if i == 0:
			cnt += arr[i] - 1
		elif arr[i] > arr[i - 1]:
			cnt += arr[i] - arr[i - 1] - 1
		if i == len(arr) - 2:
			cnt += 100 - arr[i + 1]
	print(cnt)


t = int(input())
for i in range(t):
	room = [0] * 100
	(a, b, c) = list(map(int, input().split(' ')))
	arr = list(map(int, input().split(' ')))
	dist = b * c
	for j in range(a):
		n = arr[j] - 1
		room[n] = 1
		for k in range(dist):
			if n + k + 1 < 100:
				room[n + k + 1] = 1
			if n - k - 1 > -1:
				room[n - k - 1] = 1
	print(room.count(0))


t = int(input())
for i in range(0, t):
	(m, x, y) = map(int, input().split())
	a = list(map(int, input().split()))
	f = x * y
	ans = 100
	li = []
	for j in range(1, 101):
		for k in range(0, m):
			if j in range(a[k] - f, a[k] + f + 1) and j not in li:
				ans = ans - 1
				li.append(j)
	if ans > 0:
		print(ans)
	else:
		print('0')


tests = int(input())
for i in range(tests):
	(m, x, y) = map(int, input().split())
	arr = list(map(int, input().split()))
	arr.sort()
	available_arr = [1 for i in range(101)]
	available_arr[0] = 0
	right = 0
	for j in arr:
		right_house = min(100, j + x * y) + 1
		left_house = max(0, j - x * y) - 1
		for k in range(max(j, right), right_house):
			available_arr[k] = 0
			right = k
		for k in range(j - 1, left_house, -1):
			if not available_arr[k]:
				break
			available_arr[k] = 0
	print(available_arr.count(1))