For her next karate demonstration, Ada will break some bricks.
Ada stacked three bricks on top of each other. Initially, their widths (from top to bottom) are W1,W2,W3.
Ada's strength is S. Whenever she hits a stack of bricks, consider the largest k≥0 such that the sum of widths of the topmost k bricks does not exceed S; the topmost k bricks break and are removed from the stack. Before each hit, Ada may also decide to reverse the current stack of bricks, with no cost.
Find the minimum number of hits Ada needs in order to break all bricks if she performs the reversals optimally. You are not required to minimise the number of reversals.
Input
The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
The first and only line of each test case contains four space-separated integers S, W1, W2 and W3.Output
For each test case, print a single line containing one integer ― the minimum required number of hits.Constraints
- 1≤T≤64
- 1≤S≤8
- 1≤Wi≤2 for each valid i
it is guaranteed that Ada can break all bricksExample Input

3

3 1 2 2

2 1 1 1

3 2 2 1
Example Output

2

2

2
Explanation

Example case 1:

Ada can reverse the stack and then hit it two times. Before the first hit, the widths of bricks in the stack (from top to bottom) are (2,2,1). After the first hit, the topmost brick breaks and the stack becomes (2,1). The second hit breaks both remaining bricks.

In this particular case, it is also possible to hit the stack two times without reversing. Before the first hit, it is (1,2,2). The first hit breaks the two bricks at the top (so the stack becomes (2)) and the second hit breaks the last brick.

Difficulty: interview

Starter code:

Solutions:
T = int(input())
for _ in range(T):
 W = list(map(int, input().strip().split()))
 S = W[0]
 W = W[1:]
 W = W[::-1]
 i = 0
 c = 0
 flag = 0
 while (len(W) != 0 or flag != 1) and i<len(W):
  k = i
  su = 0
  while su <= S and k<len(W)-1:
   su += W[k]
   k += 1
  if su-W[k-1]<=S:
   c += 1
  else:
   flag = 1
  i += 1
 print(c-1) 


T = int(input())
for _ in range(T):
 W = list(map(int, input().strip().split()))
 S = W[0]
 W = W[1:]
 W = W[::-1]
 i = 0
 c = 0
 flag = 0
 while (len(W) != 0 or flag != 1) and i<len(W):
  k = i
  su = 0
  while su <= S and k<len(W)-1:
   su += W[k]
   k += 1
  if su-W[k-1]<=S:
   c += 1
  else:
   flag = 1
  i += 1
 print(c-1) 


# cook your dish here
t=int(input())
while(t):
 t=t-1
 l=list(map(int,input().split()))
 S=l[0]
 W1=l[1]
 W2=l[2]
 W3=l[3]
 hits=0
 if(W1+W2+W3<=S):
  hits=1
 elif(W1+W2<=S):
  hits=2
 elif(W2+W3<=S):
  hits=2
 else:
  hits=3
 print(hits)

# cook your dish here
import math
for i in range(int(input())):
 test_list=list(map(int,input().split()))
 y=test_list.pop(0)
 print(math.ceil(sum(test_list)/y))

# cook your dish here
t=int(input())
while(t):
 t=t-1
 l=list(map(int,input().split()))
 S=l[0]
 W1=l[1]
 W2=l[2]
 W3=l[3]
 hits=0
 if(W1+W2+W3<=S):
  hits=1
 elif(W1+W2<=S):
  hits=2
 elif(W2+W3<=S):
  hits=2
 else:
  hits=3
 print(hits)

# cook your dish here
import math
for i in range(int(input())):
 li=list(map(int,input().split()))
 y=li.pop(0)
 print(math.ceil(sum(li)/y))


# cook your dish here
t=int(input())
for i in range(t):
 r=[int(x) for x in input().split()]
 [s,w1,w2,w3]=r
 x=0
 if sum(r)<=s:
  print(1)
 else:
  if (w1+w2)<=s or (w2+w3)<=s:
   print(2)
  else:
   print(3)
 
 
 
 
 
 
 




for z in range(int(input().strip())):
 a=list(map(int,input().strip().split(' ')))
 b=a[:0:-1]
 s=0
 k=0
 for i in range(len(b)):
  s+=b[i]
  if(s<a[0]):
   if(i==len(b)-1):
    k+=1
   continue
  elif(s>a[0]):
   k+=1
   s=b[i]
   if(s<a[0]):
    continue
   else:
    s=0
    k+=1
  else:
   s=0
   k+=1
 print(k)
   
   
  

   
 


# cook your dish here
a=int(input())
for i in range(a):
 l=list(map(int,input().split()))
 k=l[0]
 l.remove(l[0])
 b=0
 for i in range(len(l)-1):
  c=l[i]
  if(c<=k):
   b+=1
  c=c+l[i+1]
 print(b)

# cook your dish here
t=int(input())
for _ in range(t):
 a=[int(x) for x in input().split()]
 q=0
 c=0
 for i in range(1,4):
  if(q+a[i]<=a[0]):
   q=q+a[i]
   c+=1
  else:
   q=0
 if(c==0):
  print(1)
 else:
  print(c)

T=int(input())
res=[]
for i in range (T):
 a=input()
 a=list(a.split())
 s=int(a[0])
 w1=int(a[1])
 w2=int(a[2])
 w3=int(a[3])
 b=0
 hits=0
 if (w1+w2<=s):
  if (w1+w2+w3<=s):
   hits+=1
  else:
   hits+=2
 elif (w1+w2>s):
  if (w1<=s):
   hits+=1
  if (w2+w3>s):
   if (w2<=s):
    hits+=2
   else:
    hits+=1
  else:
   hits+=1
 b=hits
 hit=0
 if (w3+w2<=s):
  if (w1+w2+w3<=s):
   hit+=1
  else:
   hit+=2
 elif (w3+w2>s):
  if (w3<=s):
   hit+=1
  if (w2+w1>s):
   if (w2<=s):
    hit+=2
   else:
    hit+=1
  else:
   hit+=1
 if (b>hit):
  b=hit
 res.append(b)
for num in res:
 print(num)


T=int(input())
res=[]
for i in range (T):
 a=input()
 a=list(a.split())
 s=int(a[0])
 w1=int(a[1])
 w2=int(a[2])
 w3=int(a[3])
 b=0
 hits=0
 if (w1+w2<=s):
  if (w1+w2+w3<=s):
   hits+=1
  else:
   hits+=2
 elif (w1+w2>s):
  if (w1<=s):
   hits+=1
  if (w2+w3>s):
   if (w2<=s):
    hits+=2
   else:
    hits+=1
  else:
   hits+=1
 b=hits
 hit=0
 if (w3+w2<=s):
  if (w1+w2+w3<=s):
   hit+=1
  else:
   hit+=2
 elif (w3+w2>s):
  if (w3<=s):
   hit+=1
  if (w2+w1>s):
   if (w2<=s):
    hit+=2
   else:
    hit+=1
  else:
   hit+=1
 if (b>hit):
  b=hit
 res.append(b)
for num in res:
 print(num)


for _ in range(int(input())):
 s, a, b, c = list(map(int, input().split()))
 if s >= (a + b + c ):
  ans = 1
 elif s >= (a + b) or s >= (b +c):
  ans = 2
 else:
  ans = 3
 print(ans)
  


# cook your dish here
for _ in range(int(input())):
 l = list(map(int, input().split()))
 s = l[0]
 w = []
 for i in range(1, len(l)):
  w.append(l[i])
 s1 = 0
 hit = 0
 if s>=w[0]+w[1]+w[2]:
  print(1)
 elif s>=w[0]+w[1]:
  hit += 2
  print(hit)
 elif s>=w[1]+w[2]:
  hit += 2
  print(hit)
 elif s==w[0]==w[1]==w[2]:
  print(3)




# cook your dish here
n=int(input())
for i in range(n):
 s,w1,w2,w3=list(map(int,input().split()))
 if(w2>w1):
  z1=w2
 z2=min(w2,w3)
 if(s==w1+w2 and w3<=s):
  print(2)
 elif(s==w2+w3 and w1<=s):
  print(2)
 
 elif(w1==w2+w3 and w1<s):
  print(2)
 else:
  print(3)
  


for i in range(int(input())):
 count=0
 (strength,w1,w2,w3)=map(int,input().split())
 if w1+w2+w3<=strength:
  count=count+1
 elif w1+w2<=strength:
  count=count+2
 elif w1+w2>strength:
  if w2+w3<=strength:
   count=count+2
  elif w3<=strength:
   count=count+3
 elif w1<=strength:
  count=count+3
 print(count)

# cook your dish here
import math
for t in range(int(input())):
 l = [int(i) for i in input().split(" ")]
 if l[0] > sum(l[1:]):
  print(1)
 else:
  print(math.ceil(sum(l[1:])/l[0]))

x=[]
for t in range(int(input())):
 s,w1,w2,w3=list(map(int,input().strip().split()))
 z=w1+w2+w3
 c=0
 while z>0:
  z=z-s
  c=c+1
 x.append(c)
for i in x:
 print(i)
  


t=int(input())
for i in range(t):
 list1=list(map(int,input().split()))
 s=list1[0]
 list2=list1[1:]
 if(sum(list2)<=list1[0]):
  print("1")
 else:
  
  if(list2[0]+list2[1]<=s and list2[2]<=s):
   print("2")
  elif(list2[2]+list2[1]<=s and list2[0]<=s):
   print("2")
  elif(list2[0]<=s and list2[1]<=s and list2[2]<=s):
   print("3")

# cook your dish here
import collections


def hit(bricks):
 if len(bricks) == 3:
  if sum(bricks) <= S:
   bricks.clear()
  else:
   if bricks[0] + bricks[1] <= S:
    bricks.popleft()
    bricks.popleft()
   else:
    if bricks[1] + bricks[2] <= S:
     bricks.pop()
     bricks.pop()
    else:
     if bricks[2] <= S:
      bricks.pop()
 elif len(bricks) == 2:
  if bricks[0] + bricks[1] <= S:
   bricks.popleft()
   bricks.popleft()
  else:
   if bricks[1] <= S:
    bricks.pop()
 elif len(bricks) == 1:
  if bricks[0] <= S:
   bricks.pop()
  else:
   raise ValueError("Last brick too stronk")

 return bricks


T = int(input())

for _ in range(T):
 S, W1, W2, W3 = list(map(int, input().split()))
 bricks = collections.deque([W1, W2, W3])
 count = 0

 while len(bricks) > 0:
  bricks = hit(bricks)
  count += 1

 print(count)


t=int(input())
for i in range(t):
 s,w1,w2,w3=list(map(int, input().split()))
 list1=[]
 list1.append(w1)
 list1.append(w2)
 list1.append(w3)
 list1.sort()
 if((list1[0]+list1[1]+list1[2])<=s):
  print(1)
 elif((list1[0]+list1[1])<=s):
  print(2)
 else:
  print(3)


for _ in range(int(input())):
 s,a,b,c=list(map(int,input().split()))
 l=[]
 l.extend([c,b,a])
 c=0
 sum=0
 for i in range(3):
  x=l.pop()
  sum+=x
  if sum<s:
   pass
  elif sum==s:
   c+=1
   sum=0
  else:
   c+=1
   sum=x
 if sum<s and sum!=0:
  c+=1
 print(c)
   


# n,k = map(int,input().strip().split(" ")) takes two number as input in a     single line
# arr = list(map(int,input().split())) takes an array as a input in a single     line
# arr = [int(input()) for i in range(n)] takes an array as input in different     lines


def solve() :
 s,w1,w2,w3 = list(map(int,input().split()))
 k = w1+w2+w3
 if k<=s :
  ans = 1
 elif (k-w3 <= s) or (k-w1 <= s) :
  ans = 2
 else :
  ans = 3
 print(ans)
 
t = int(input())
while t>0 :
 solve()
 t -= 1


# cook your dish here
for i in range(0,int(input())):
 power,x,y,z=list(map(float,input().split()))
 summ=x+y+z
 a=x+y
 b=y+z
 flagg=0
 if(x==y and y==z):
  flagg==0
 
 else:
  flagg=0
 
 if(power>=summ):
  print('1')
 else:
  if(flagg==1):
   if((x+y)>=power):
    print('2')
   else:
    print('3')
  else:
   
   if((power-z)>=y):
    
    print('2')
    
   else:
    if((power-y)>=x):
     print('2')
    else:
     print('3')

# cook your dish here
for i in range(int(input())):
 s,w1,w2,w3=map(int,input().split())
 if s>= w1+w2+w3:
  print(1)
 else:
  if s>= w1+w2:
   if s>=w3:
    print(2)
   else:
    print(1+w3//s)
  elif s>=w2+w3:
   if s>=w1:
    print(2)
   else:
    print(1+w1//s)
  else:
   print(w1//s+w2//s+w3//s)