번개맨 쉼터

if __name__ == '__main__':
    T = int(input()) # 테스트 케이스의 수 T<=100
    for _ in range(T):
        N,M = map(int,input().split())
        for _ in range(M):
            input()
        print(N-1)

from collections import deque
def solution():
    find = False
    # BFS 로
    while not_visited: #  전부 방문시
        nx,ny = not_visited.popleft()
        #print(nx,ny)
        for x,y in zip(dx,dy):
            if 0<= nx+x <= length-1 and 0<= ny+y <=length-1:
                if graph[nx+x][ny+y] != 0:
                    continue
                elif nx+x == target_night[0] and ny+y == target_night[1]:
                    graph[nx+x][ny+y] = graph[nx][ny] + 1
                    return graph[target_night[0]][target_night[1]]-1
                else:
                    graph[nx+x][ny+y] = graph[nx][ny] + 1
                    not_visited.append([nx+x,ny+y])
            #print(not_visited)
    return 0

if __name__ == '__main__':
    N = int(input()) # 테스트 케이스의 개수
    
    # 이동 가능 방법 표시
    dx = [1,2,2,1,-1,-2,-2,-1]
    dy = [2,1,-1,-2,-2,-1,1,2]
    
    for _ in range(N):
        length = int(input()) # 체스판 한 변의 길이 ㅇ(4 <= I <= 300)
        cur_night = list(map(int,(input().split()))) # 현재 나이트가 있는 칸
        target_night = list(map(int,(input().split()))) # 현재 나이트가 있는 칸
        graph = [[0 for _ in range(length)] for _ in range(length)]; graph[cur_night[0]][cur_night[1]] = 1
        not_visited = deque(); not_visited.append((cur_night)) # 초기 설정
        print(solution())

# 규칙
# 1번 . 계단은 한번에 한계단 or 두 계단
# 2번 . 연속된 세 개의 계단을 모두 밟아서는 안된다. (시작점 제외)
# 3번 . 마지막 도착 계단은 반드시 밟아야 한다.

def dfs(idx,cost,conn):
    global answer
    if conn >= 3:
        return
    if idx == N-1:
        answer = max(answer,cost)
    for i in range(1,3):
        if idx + i > N-1:
            return
        if idx == -1:
            dfs(idx+i,cost + score_list[idx+i],conn+1)
            continue
        elif i == 1:
            dfs(idx+i,cost + score_list[idx+i],conn+1)
        else:
            dfs(idx+i,cost + score_list[idx+i],1)

if __name__ == '__main__':
    score_list = []; answer =0
    N = int(input()) # 계단의 개수 <= 300
    for idx in range(N): # 점수 <= 10,000
        score_list.append(int(input()))
    

    dfs(-1,0,0)
    print(answer)

    
# [0,1] [0,2] [1,2] [1,3] [2,3] [2,4]
# [3,4] [3,5] [4,5] [4,6]

def is_promising(x):
    for i in range(x):
        if row[x] == row[i] or abs(row[x] - row[i]) == abs(x-i):
            return False
        
        return True

def n_queens(n,x):
    global ans
    if x == n:
        ans +=1
    else:
        for i in range(n):
            row[x] = i
            if is_promising(x):
                n_queens(n,x+1)


if __name__ == '__main__':
    N = int(input()) # 1<= N < 15
    
    ans = 0
    row = [0] * N

    n_queens(N,0)