Read problem statements in [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

Chef has 3 boxes of sizes A, B, and C respectively. He puts the boxes in bags of size D (A ≤ B ≤ C ≤ D). Find the minimum number of bags Chef needs so that he can put each box in a bag. A bag can contain more than one box if the sum of sizes of boxes in the bag does not exceed the size of the bag.

------ Input Format ------ 

- The first line contains T denoting the number of test cases. Then the test cases follow.
- Each test case contains four integers A, B, C, and D on a single line denoting the sizes of the boxes and bags.

------ Output Format ------ 

For each test case, output on a single line the minimum number of bags Chef needs.

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

$1≤ T ≤ 100$
$1 ≤ A ≤ B ≤ C ≤ D ≤ 100$

------ subtasks ------ 

Subtask 1 (100 points): Original constraints

----- Sample Input 1 ------ 
3
2 3 5 10
1 2 3 5
3 3 4 4

----- Sample Output 1 ------ 
1
2
3

----- explanation 1 ------ 
Test case $1$:  The sum of sizes of boxes is $2 + 3 + 5 = 10$ which is equal to the size of a bag. Hence Chef can put all three boxes in a single bag.

Test case $2$: Chef can put boxes of size $1$ and $3$ in one bag and box of size $2$ in another bag.

Test case $3$: Chef puts all the boxes in separate bags as there is no way to put more than one box in a single bag.

Source: codechef | Difficulty: EASY
Tags: Mathematics

Ad-hoc


Solutions:
for _ in range(int(input())):
	(a, b, c, d) = map(int, input().split())
	if a + b + c <= d:
		print(1)
	elif a + b <= d or b + c <= d or a + c <= d:
		print(2)
	else:
		print(3)


for _ in range(int(input())):
	(a, b, c, d) = map(int, input().split())
	l = 0
	if d - c < b:
		l = 1
		if d - b < a:
			l = 2
	elif d - c - b < a:
		l = 1
	print(1 + l)


import math
T = int(input())
for i in range(T):
	(a, b, c, d) = map(int, input().split())
	x = a + b + c
	if x <= d:
		print('1')
	elif a + b <= d or a + c <= d or b + c <= d:
		print('2')
	else:
		print('3')


n = int(input())
for i in range(n):
	(a, b, c, d) = list(map(int, input().split()))
	c1 = 0
	if a + b + c <= d:
		print('1')
	else:
		if a + b <= d or b + c <= d or a + c <= d:
			c1 += 1
		else:
			c1 = 2
		print(c1 + 1)


t = int(input())
for i in range(t):
	(a, b, c, d) = map(int, input().split())
	if a + b + c <= d:
		print('1')
	elif a + b + c > d and a + b <= d:
		print('2')
	else:
		print('3')


T = int(input())
for i in range(T):
	(a, b, c, d) = map(int, input().split())
	total = a + b + c
	if total <= d:
		count = 1
	elif a + b <= d:
		count = 2
	else:
		count = 3
	print(count)


t = int(input())
while t:
	t -= 1
	(a, b, c, d) = tuple(map(int, input().split()))
	d = d - a
	if d >= b:
		d = d - b
		if d >= c:
			print(1)
		else:
			print(2)
	else:
		print(3)


for _____cases_____ in range(int(input())):
	(A, B, C, D) = map(int, input().split())
	limit1 = A + B
	limit2 = limit1 + C
	if limit1 <= D:
		print(1 if limit2 <= D else 2)
	else:
		print(3)


t = int(input())
for i in range(t):
	(a, b, c, d) = map(int, input().split())
	z = a + b
	y = z + c
	if z <= d:
		if y <= d:
			print(1)
		else:
			print(2)
	else:
		print(3)


import math
t = int(input())
for _ in range(t):
	(a, b, c, d) = map(int, input().split())
	s = a + b + c
	if s <= d:
		print(1)
	elif a + b <= d or b + c <= d or a + c <= d:
		print(2)
	else:
		print(3)


T = int(input())
a = b = c = d = None
s = ''
for i in range(T):
	s = input() + ' '
	cnt = 0
	k = ''
	for i in range(len(s)):
		if s[i] != ' ':
			k = k + s[i]
		else:
			cnt += 1
			if cnt == 1:
				a = int(k)
			elif cnt == 2:
				b = int(k)
			elif cnt == 3:
				c = int(k)
			elif cnt == 4:
				d = int(k)
			k = ''
	cnt = 0
	if a + b + c <= d:
		print(1)
	elif a + b <= d or b + c <= d or c + a <= d:
		print(2)
	else:
		print(3)


t = int(input())
while t > 0:
	(a, b, c, d) = input().split()
	(a, b, c, d) = [int(a), int(b), int(c), int(d)]
	if a + b + c <= d:
		print(1)
	elif a + b <= d or a + c <= d or b + c <= d:
		print(2)
	else:
		print(3)
	t = t - 1


for _ in range(int(input())):
	l = list(map(int, input().split(' ')))
	b = l.pop()
	ba = b
	count = 0
	b -= l[0]
	count += 1
	if b < l[1]:
		ba -= l[1]
		count += 1
	else:
		b -= l[1]
	if count == 1 and b >= l[2]:
		print(count)
	elif count == 2 and (ba >= l[2] or b >= l[2]):
		print(count)
	else:
		count += 1
		print(count)


t = int(input())
while t:
	(a, b, c, d) = map(int, input().split())
	if a <= d and a + b > d:
		print('3')
	elif a + b <= d and a + b + c > d:
		print('2')
	else:
		print('1')
	t -= 1


t = int(input(''))
for i in range(t):
	s = input('')
	s = s.split(' ')
	(a, b, c, d) = (int(s[0]), int(s[1]), int(s[2]), int(s[3]))
	if a + b + c <= d:
		print('1')
	elif a + b <= d or c + b <= d or a + c <= d:
		print('2')
	else:
		print('3')


t = int(input())
for i in range(t):
	bag = 0
	(a, b, c, d) = list(map(int, input().split()))
	if a + c <= d:
		if a + c + b <= d:
			bag += 1
		else:
			bag += 2
	elif a + b <= d:
		bag += 2
	else:
		bag += 3
	print(bag)


for test in range(int(input())):
	lt = list(map(int, input().split()))
	quantity = lt[0] + lt[1] + lt[2]
	bagSize = lt[3]
	noBags = quantity // bagSize
	if quantity <= bagSize:
		noBags = 1
	elif lt[0] + lt[1] <= bagSize or lt[0] + lt[2] <= bagSize:
		noBags = 2
	else:
		noBags = 3
	print(noBags)


for tc in range(int(input())):
	arr = list(map(int, input().split()))
	sum = 0
	bag = arr[3]
	c = 1
	for i in range(3):
		if sum + arr[i] <= bag:
			sum = sum + arr[i]
		else:
			c = c + 1
	print(c)


T = int(input())
for _ in range(T):
	(A, B, C, D) = map(int, input().split())
	b = 1
	tot = 0
	for i in (A, B, C):
		tot += i
		if tot > D:
			b += 1
	print(b)


G = int(input())
while G > 0:
	(A, B, C, D) = map(int, input().split())
	count = 0
	if A + B + C <= D:
		count = 1
	elif A + B <= D or A + C <= D or B + C <= D:
		count = 2
	else:
		count = 3
	print(count)
	G -= 1


n = int(input())
for i in range(n):
	(a, b, c, d) = list(map(int, input().split()))
	if a + b <= d:
		if a + b + c <= d:
			print('1')
		else:
			print('2')
	else:
		print('3')


import math
t = int(input())
for i in range(t):
	(a, b, c, d) = map(int, input().split())
	sum1 = a + b + c
	sum2 = a + b
	if sum1 <= d:
		print(1)
	elif sum2 <= d:
		print(2)
	else:
		print(3)


for _ in range(int(input())):
	l = list(map(int, input().split()))
	a = l.pop()
	l.sort()
	if l[0] + l[1] + l[2] <= a:
		print(1)
	elif l[0] + l[1] <= a:
		print(2)
	else:
		print(3)


def solve(a, b, c, d):
	sm = a
	a = 0
	ct = 0
	while True:
		if sm + b <= d:
			sm += b
			b = 0
		if sm + c <= d:
			sm += c
			c = 0
		if sm <= d:
			sm = 0
			ct += 1
		if a == 0 and b == 0 and (c == 0):
			break
	return ct

def main():
	n = int(input())
	while n:
		n -= 1
		(a, b, c, d) = map(int, input().split())
		print(solve(a, b, c, d))
main()


for nt in range(int(input())):
	(b1, b2, b3, bs) = map(int, input().split())
	if b1 + b2 + b3 <= bs:
		print('1')
	elif b1 + b2 <= bs or b2 + b3 <= bs or b1 + b3 <= bs:
		print('2')
	else:
		print('3')


for i in range(int(input())):
	(A, B, C, D) = map(int, input().split())
	if A + B + C <= D:
		print(1)
	elif A + B <= D:
		print(2)
	else:
		print(3)


T = int(input())
while T > 0:
	(a, b, c, d) = map(int, input().split())
	if a + b + c <= d:
		print(1)
	elif a + b <= d:
		print(2)
	else:
		print(3)
	T = T - 1