T = int(input())
# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
for test_case in range(1, T + 1):
    # ///////////////////////////////////////////////////////////////////////////////////
    n, k, b = map(int, input().split())
    B = []
    for i in range(n+1):
    	B.append( [0] * (i+1)  )
    	for j in range(min(a,i)+1):
       		if j==0 or j == i: B[i][j] = 1
            else: B[i][j]  = B[i-1][j-1]  + B[i-1][j]
	print(B[i][j])

  def make_one(a):
    a = int(a)
    if a == 2 or a == 3 or a == 1:
        m[a] = 1
    elif m[a]==0:
        temp = []
        if a%3 == 0:
            temp.append(1+make_one(a/3))
        if a%2 == 0:
            temp.append(1+make_one(a/2))
        temp.append(1+make_one(a-1))
        m[a] = min(temp)
    return m[a]

n = int(input()) # 입력받은 값
m = [0]*(n+1)
print(make_one(n))

  def block(num):
    if num ==1 or num==2:
        count[num] = num
    if count[num] == 0:
        count[num] = block(num-1)+block(num-2)
    return count[num]

n = int(input())
count = [ 0 for i in range(n+1)]
print(block(n)% 10007)

n = int(input())
count = [0,1,3]
for i in range(3,n+1):
    count[i] = count[i-1]+count[i-2]*2
print(count[n]% 10007)

n = int(input())
juice = []
for i in range(6):
    temp  = int(input())
    juice.append(temp)
check = [False]*n
count = 0
for i in range(len(check)):
    if check[i-1] and check[i-2]:
        continue
    else:
        count+=juice[i]
        check[i] = True
print(count%10009)

n = int(input())
count = 0
for i in range(len(check)):
    if check[i-1] and check[i-2]:
        continue
    else:
        count += check[i]
        check[i] = True
result = [0,juice[0]]
check =[]
for i in range(1,n):
    for j in range(len(result)):
        if (i-1) in check and (i-2) in check:
            continue
        else:
            result[j] +=juice[i]
            check.append(i)
    result.append(juice[i])
print(max(result))

n = int(input())
count = 0
result = [0] # 각 자리수의 최대의 와인량
for i in range(1,n+1):
    if i==1:
        result.append(juice[i-1])
    elif i==2:
        result.append(juice[i-1]+juice[i-2])
    else:
        result.append(max(result[i-1], # 이번 잔은 안먹는 경우
                         result[i-2]+juice[i-1], # 이번에는 먹었지만 저번엔 안먹은 경우
                         result[i-3]+juice[i-1]+juice[i-2])) # 저번에도 먹고 이번에도 먹는 경우
print(result[n])

num = str(input())
result = [0]*len(num)
for i in range(len(num)):
    if i == 0:
        if num[i]=='0':
            break
        else: result[i] = 1
    else:
        temp = int(num[i-1:i+1])
        if num[i] == '0':
            if temp !=10 or temp!=20: break
            else: result[i] = result[i-2]
        elif temp < 27 and temp >10:
            if i == 1: result[i] =2
            else: result[i] = (result[i-2]+result[i-1])
        else:
            result[i] = result[i-1]
print(result[-1])