# 데이터 입력받기
nodes = input().split()
# 루트 : 왼쪽자식, 오른쪽자식으로 저장
tree[nodes[0]] = [nodes[1], nodes[2]]

# https://www.acmicpc.net/problem/1991

n = int(input())

# 트리로 사용할 딕셔너리 생성
tree = {}


# 전위순회 VLR
def preorder(root):
    # .이 아닐때만 출력
    if root != '.':
        print(root, end='')  # v
        preorder(tree[root][0])  # L
        preorder(tree[root][1])  # R


# 중위순회 LVR
def inorder(root):
    # .이 아닐때만 출력
    if root != '.':
        inorder(tree[root][0])  # L
        print(root, end='')  # v
        inorder(tree[root][1])  # R


# 후위순회 LRV
def postorder(root):
    # .이 아닐때만 출력
    if root != '.':
        postorder(tree[root][0])  # L
        postorder(tree[root][1])  # R
        print(root, end='')  # v


for _ in range(n):
    # 데이터 입력받기
    nodes = input().split()
    # 루트 : 왼쪽자식, 오른쪽자식으로 저장
    tree[nodes[0]] = [nodes[1], nodes[2]]

# 결과 출력
preorder('A')
print()
inorder('A')
print()
postorder('A')

# 카드의 개수 입력받기
n = int(input())

# 카드 리스트 입력받기
card_list = list(map(int, input().split()))

# 탐색할 카드의 개수 입력받기
m = int(input())

# 탐색할 카드 리스트 입력받기
search_list = list(map(int, input().split()))

# 이분 탐색을 이용하기 위해 카드리스트를 정렬한다.
card_list.sort()

for i in range(len(search_list)):
    # 탐색할 가드 선정
    card = search_list[i]

    # 이분탐색 시작
    start = 0  # 시작 인덱스
    end = len(card_list)  # 마지막 인덱스

    for j in range(start, end):

        # 탐색 종료 조건 설정
        if start >= end:
            # 탐색 실패
            search_list[i] = 0
            break

        # 가운데 인덱스 선택
        middle = (start+end)//2

        # 가운데 값이 탐색카드와 같을때 => 탐색종료
        if card == card_list[middle]:
            # 탐색 성공
            search_list[i] = 1
            break
        # 가운데 카드보다 탐색카드가 클때
        elif card > card_list[middle]:
            # 탐색 범위 수정
            start = middle+1

        # 가운데 카드보다 탐색카드가 작을때
        elif card < card_list[middle]:
            end = middle


# 탐색 결과 출력
for card in search_list:
    print(card, end=" ")

# https://www.acmicpc.net/problem/9461

'''
오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 길이를 k라 했을 때, 그 변에 길이가 k인 정삼각형을 추가한다.

파도반 수열 P(N)은 나선에 있는 정삼각형의 변의 길이이다. P(1)부터 P(10)까지 첫 10개 숫자는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9이다.

N이 주어졌을 때, P(N)을 구하는 프로그램을 작성하시오.

입력
첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고,
N이 주어진다. (1 ≤ N ≤ 100)

출력
각 테스트 케이스마다 P(N)을 출력한다.

'''

# 테스트 케이스의 개수
t = int(input())

# dp 테이블 작성
# n은 최대 100
dp = [0]*101 # 0~100

# 이전 숫자에 영향을 받지 않는 데이터들은 미리 기록
dp[0] = 1
dp[1] = 1
dp[2] = 1
dp[3] = 2
dp[4] = 2

# 테스트 케이스만큼 반복
for _ in range(t):
    n = int(input())
    # 알고리즘 시작
    for i in range(5,n+1):
        if dp[i] != 0: # dp테이블에 이미 값이 기록된경우는 무시한다.
            continue
        # 점화식에 따라 아래와 같이 수행한다. 
        # => 5번째로 그리는 도형부터 이전숫자와 0번부터 올라가는 구조이므로
        dp[i] = dp[i-1] + dp[i-5] 
    
    print(dp[n-1])

n = int(input())

dp = [0]*(n)  # 누적합을 저장할 배열

data = list(map(int, input().split()))

dp[0] = data[0]  # 첫번째 dp의 값은 첫번째 데이터와 같음

# 입력받은 data의 각 인덱스에서 dp값이 가장 큰 인덱스에 현재 데이터를 누적시켜 더한다.

for i in range(1, n):
    for j in range(i):
        # 만족해야 하는 조건
        # 이전의 숫자들이 현재 숫자들보다 작은 숫자일것
        # 이전 숫자들중 가장 큰 값까지 이뤄지는 수열일것 => 그리고 이들의 누적합을 구해야함
        if data[j] < data[i] and dp[j] > dp[i]:
            dp[i] = dp[j]  # dp값 업데이트
    dp[i] += data[i]  # 현재 인덱스의 값을 누적합에 더한다.

print(max(dp))  # dp에 기록된 수중 가장 큰 값이, 가장 큰 합이 될 것

n = int(input())

# dp 테이블 작성
dp = [0]*(n+1)

for i in range(1, n+1):
    if i == 1:
        dp[i] = 1  # 2 x 1 크기는 1개
    elif i == 2:
        dp[i] = 3  # 2 x 2 크기는 3개(||,=,ㅁ)
    else:
        dp[i] = dp[i-1] + 2*dp[i-2]  # i-2인 경우는 =이 붙거나 ㅁ이 붙을수 있기 때문에

# 모듈러 연산하여 출력
print(dp[n] % 10007)

n = int(input())

# dp테이블 생성
dp = [0]*(n+1)

# n이 3이상인 경우에 대해서는 다음과 같이 생각할수 있다
# 2 x (n-1)인 도형에 일자 막대를 붙이는 경우 => dp[n-1]과 개수가 같다(일자 막대를 이어붙일 뿐이므로)
# 2 x (n-2)인 도형에 가로막대 2개(=모양)을 붙이는 경우 => dp[n-2]과 개수가 같다
# 따라서 점화식은 다음과 같다 dp[n] = dp[n-1] + dp[n-2]

for i in range(1, n+1):
    if i == 1:
        # 2 x 1인 도형을 만들 수 있는 경우의 수
        dp[i] = 1
    elif i == 2:
        # 2 x 2인 도형을 만들 수 있는 경우의 수
        dp[i] = 2  # ||,= 두가지 형태가 가능
    else:
        dp[i] = (dp[i-1] + dp[i-2]) % 10007  # 모듈러 연산하여 저장(문제의 조건)

print(dp[n] % 10007)

n = int(input())

# 앞자리 수가 i인 n자리 계단수의 개수는 다음과 같이 표현한다
# dp[n][i]
# 이때 i는 1~9까지 가능함

# 수를 저장할 2차원 배열 작성
# n은 1보다 크고 100보다 작거나 같은 수
dp = [[0]*10 for _ in range(101)]

# 한자리 계단 수의 개수 기록
for i in range(10):
    dp[1][i] = 1
    
# 알고리즘 수행

# n자리 수가 될때까지 계단수 dp테이블에 작성
for i in range(2, n+1):  # 3~n자리 계단수 계산
    # 앞자리수가 될 수 있는 조건은 1~9까지의 수 => i에 대입하여 기록
    # 다음 수의 계산을 위해 앞자리수가 0인 계단수도 기록은 해둔다.
    for j in range(10):
        # 앞자리수가 0인 경위와 9인 경우는 뒤의수가 1과 8만이 가능하므로 별도로 기록한다.
        if j == 0:
            dp[i][j] = dp[i-1][1]  # 1인 경우만 가능
        elif j == 9:
            dp[i][j] = dp[i-1][8]  # 8인 경우만 가능
        else:
            # 2인 경우 1과 3이 가능(+-1인 쌍이 존재) 
            dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1]

# => 오버플로우 방지를 위하여 %1000000000 하여 출력
# 결과 출력 n자리 계단수들의 합 => 앞자리 수가 0인 경우는 계단수로 취급하지 않으므로 빼준다.
print((sum(dp[n])-dp[n][0]) % 1000000000)

n = int(input())

# dp테이블 생성
# n자리수까지 고려
dp = [[0]*10 for _ in range(1001)]

# 1자리 수의 경우는 0~9로 10개이다.
dp[1] = 10
# 2자리 수의 경우는 앞자리 수에 따라 달라진다.
for i in range(10):  # 앞자리 수는 0~9가 될 수 있다.
    # 앞자리수가 i일때의 2자리 수의 오르막수의 개수는 다음과 같이 표현한다.
    dp[2][i] = (dp[1] - i)

# 3자리수 이상부터 알고리즘시작(2자리수까지는 이미 계산되어있으므로)
for k in range(3, n+1):  # n자리수까지 작동
    for i in range(10):  # 앞자리 수는 0~9가 될 수 있다.
        for j in range(i, 10):
            dp[k][i] += (dp[k-1][j] % 10007)  # 모듈러 연산시행하여 저장(오버플로우 방지)

# 정답 출력
if n == 1:
    print(10)
else:
    print(sum(dp[n]) % 10007)

# https://www.acmicpc.net/problem/10828

# 시간초과판정을 받지 않기 위하여(입력에 걸리는 시간을 단축하기 위해)
import sys
input = sys.stdin.readline

# 스택의 역할을 할 리스트 생성
stack = []

# 명령의 횟수
n = int(input())

# len 명령을 최대한 줄이기 위해 스택의 크기를 측정할 변수 생성
count = 0

for i in range(n):
    # 명령 입력받기
    command = list(map(str, input().split()))
    # push 명령이 존재한다면 숫자와 분할
    if command[0] == "push":
        stack.append(int(command[1]))
        count += 1  # 스택 내용물 추가
    elif command[0] == "top":
        # 스택이 비어있다면 -1 출력
        if count == 0:
            print(-1)
        else:
            # 가장 위에 있는 정수 출력
            print(stack[-1])
    elif command[0] == "size":
        # 스택의 크기를 출력한다.
        print(count)
    elif command[0] == "empty":
        # 스택이 비어있으면 1을 출력하고 아니면 0을 출력한다.
        if count == 0:
            print(1)
        else:
            print(0)
    elif command[0] == "pop":
        # 스택이 비어있다면
        if count == 0:
            print(-1)
        else:  # 스택이 비어있지 않다면
            print(stack.pop())
            count -= 1

# 큐 자료구조를 쓰기 위해 덱을 import
from collections import deque

# 큐 생성
queue = deque()

# bfs를 수행하기위해 함수 정의

# 네 방향을 지정하기 위함
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def bfs(graph):
    global m, n
    global queue
    # 큐에 값이 존재하는동안 탐색 진행
    while queue:
        node = queue.popleft()
        x, y = node[0], node[1]
        for i in range(4):
            # 상,하,좌,우에 대해 탐색 진행
            mx = x + dx[i]
            my = y + dy[i]
            if 0 <= mx < n and 0 <= my < m:  # 영역을 벗어나지 않는지 확인
                # 안익은 토마토만 익게하면 됨(안익은 토마토는 0)
                if graph[mx][my] == 0:
                    graph[mx][my] = graph[x][y] + 1  # 토마토를 익게함
                    queue.append([mx, my])


m, n = map(int, input().split())

graph = [list(map(int, input().split())) for _ in range(n)]

# 그래프 탐색을 진행하며 정수 1이 익은 토마토를 의미하므로,
# 하루가 지난후 익은 토마토의 영향을 받아 익은 토마토를 2로, 2 토마토에 영향을 받은 토마토를 3토마토로 증가하여 표현한다.
# 탐색 종료이후 그래프의 최대값을 출력하면, 최소일수와 관련있을것 => 단 2차원 그래프인점을 고려하여 출력
# # 탐색 종료 이후 그래프에 0인 토마토가 존재한다면 익지 않은 토마토가 있다는 의미이므로 -1을 출력하고, 그렇지 않다면 최소일수를 출력한다.

# 모든 정점을하나씩 방문하며 탐색 진행
for i in range(n):
    for j in range(m):
        if graph[i][j] == 1:
            # 탐색할 목록에 넣어두기 => 바로 bfs를 시행하지 않고, 날짜순으로 수행하기위해 담아만 둔다.
            queue.append([i, j])

# 1인 토마토에 대해 탐색 진행
bfs(graph)

# 안 익은 토마토(0)가 있는지 탐색하기 위함
isZero = False
minDate = 0  # 토마토가 다 익는데 걸리는 최소 일수를 기록하기 위함

# 안익은 토마토의 존재유무와 최소일수 계산
for g in graph:
    # 2차원 배열에서 한 줄 씩 검사를 실시한다 => 0인 토마토가 있는지
    if 0 in g:
        isZero = True
        break
    if minDate < max(g):
        # 최소일수를 구하기 위해
        minDate = max(g)

if isZero:
    print(-1)
else:
    # 모든 토마토가 다 익으면 최소일수를 출력한다.
    print(minDate-1)  # 마지막날짜에 +1 된 값이 들어가므로 -1을 해줌

# 큐 자료구조를 쓰기 위해 덱을 import
from collections import deque

# 큐 생성
queue = deque()

# 네 방향을 지정하기 위함
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

m, n = map(int, input().split())

graph = [list(map(int, input().split())) for _ in range(n)]

# 모든 정점을하나씩 방문하며 탐색 진행
for i in range(n):
    for j in range(m):
        if graph[i][j] == 1:
            # 탐색할 목록에 넣어두기 => 바로 bfs를 시행하지 않고, 날짜순으로 수행하기위해 담아만 둔다.
            queue.append([i, j])

# 1인 토마토에 대해 탐색 진행
bfs(graph)

def bfs(graph):
    global m, n
    global queue
    # 큐에 값이 존재하는동안 탐색 진행
    while queue:
        node = queue.popleft()
        x, y = node[0], node[1]
        for i in range(4):
            # 상,하,좌,우에 대해 탐색 진행
            mx = x + dx[i]
            my = y + dy[i]
            if 0 <= mx < n and 0 <= my < m:  # 영역을 벗어나지 않는지 확인
                # 안익은 토마토만 익게하면 됨(안익은 토마토는 0)
                if graph[mx][my] == 0:
                    graph[mx][my] = graph[x][y] + 1  # 토마토를 익게함
                    queue.append([mx, my])

# 안익은 토마토의 존재유무와 최소일수 계산
for g in graph:
    # 2차원 배열에서 한 줄 씩 검사를 실시한다 => 0인 토마토가 있는지
    if 0 in g:
        isZero = True
        break
    if minDate < max(g):
        # 최소일수를 구하기 위해
        minDate = max(g)

if isZero:
    print(-1)
else:
    # 모든 토마토가 다 익으면 최소일수를 출력한다.
    print(minDate-1)  # 마지막날짜에 +1 된 값이 들어가므로 -1을 해줌