# 프로그래머스 문제 '베스트앨범'
# https://programmers.co.kr/learn/courses/30/lessons/42579

class Song:

    def __init__(self, song_num, genre, play):
        self.song_num = song_num
        self.genre = genre
        self.play = play
    

def solution(genres, plays):
    genre_dict = {}
    genre_list = []

    for song_num, genre, play in zip(range(len(genres)), genres, plays):
        song = Song(song_num, genre, play)

        if not genre_dict.get(genre):
            genre_list.append(genre)
            genre_dict[genre] = {'total_plays': 0, 'song_list': []}
        
        genre_dict[genre]['total_plays'] += play
        genre_dict[genre]['song_list'].append(song)

    genre_list.sort(reverse=True, key=lambda genre: genre_dict[genre]['total_plays'])

    best_album = []
    for genre in genre_list:
        song_list = genre_dict[genre]['song_list']
        song_list.sort(reverse=True, key=lambda song: (song.play, -song.song_num))
        best_songs = song_list[:2]
        for song in best_songs:
            best_album.append(song.song_num)
    
    return best_album



def solution2(genres, plays):
    genre_dict = {}
    genre_list = []

    for song_num, genre, play in zip(range(len(genres)), genres, plays):
        song = Song(song_num, genre, play)

        if not genre_dict.get(genre):
            genre_dict[genre] = {'total_plays': 0, 'best_songs': [Song(-1, genre, -1), Song(-1, genre, -1)]}
            genre_list.append(genre)

        genre_dict[genre]['total_plays'] += play

        best_songs = genre_dict[genre]['best_songs']
        if best_songs[0].play < play:
            best_songs[1] = best_songs[0]
            best_songs[0] = song
            continue

        if best_songs[0].play == play:
            if best_songs[0].song_num > song_num:
                best_songs[1] = best_songs[0]
                best_songs[0] = song
                continue
        
        if best_songs[1].play < play:
            best_songs[1] = song
            continue
        
        if best_songs[1].play == play:
            if best_songs[1].song_num > song_num:
                best_songs[1] = song

    genre_list.sort(reverse=True, key=lambda genre: genre_dict[genre]['total_plays'])

    best_album = []

    for genre in genre_list:
        best_songs = genre_dict[genre]['best_songs']
        for song in best_songs:
            if song.play >= 0:
                best_album.append(song.song_num)

    return best_album


if __name__=='__main__':

    genres = ["classic", "pop", "classic", "classic", "pop"]
    plays = [500, 600, 150, 800, 2500]
    answer = [4, 1, 3, 0]
    my_answer = solution(genres, plays)

    print(f'answer: {answer}, my_answer: {my_answer}')

T = int(input())

mirror = {
    'b': 'd',
    'd': 'b',
    'p': 'q',
    'q': 'p'
}

for t in range(1, T+1):
    word = input()

    result = ''
    for i in range(len(word) - 1, -1, -1):
        result += mirror[word[i]]

    print('#{} {}'.format(t, result))

T = int(input())

for t in range(1, T+1):
    N, K = map(int, input().split())
    MAP = [[0 for _ in range(N+2)] for _ in range(N+2)]

    for i in range(1, N+1):
        MAP[i][1:-1] = map(int, input().split())

    cnt_list = [0 for _ in range(N + 1)]
    for i in range(1, N+1):
        # row
        j = 1
        while j <= N:
            cnt = 0
            while MAP[i][j]:
                cnt += 1
                j += 1
            cnt_list[cnt] += 1
            j += 1

        # col
        j = 1
        while j <= N:
            cnt = 0
            while MAP[j][i]:
                cnt += 1
                j += 1
            cnt_list[cnt] += 1
            j += 1


    print('#{} {}'.format(t, cnt_list[K]))

방법 1) bubble sort

def bubble_sort(lst):
    for i in range(1, len(lst)):
        for j in range(len(lst) - i):
            if lst[j] > lst[j + 1]:
                lst[j], lst[j + 1] = lst[j + 1], lst[j]

    return lst

if __name__=='__main__':
    T = int(input())

    for t in range(1, T + 1):
        N = int(input())
        lst = list(map(int, input().split()))

        bubble_sort(lst)

        print('#{}'.format(t), end=' ')
        print(*lst, sep=' ')

방법 2) selection sort

def selection_sort(lst):
    for i in range(len(lst) - 1):
        for j in range(i + 1, len(lst)):
            if lst[i] > lst[j]:
                lst[i], lst[j] = lst[j], lst[i]

    return lst

if __name__=='__main__':
    T = int(input())

    for t in range(1, T + 1):
        N = int(input())
        lst = list(map(int, input().split()))

        selection_sort(lst)

        print('#{}'.format(t), end=' ')
        print(*lst, sep=' ')

방법 3) merge sort

def merge_sort(lst, l, r):
    if r - l <= 1:
        return

    c = (l + r) // 2

    merge_sort(lst, l, c)
    merge_sort(lst, c, r)

    l_ptr = l
    r_ptr = c
    tmp_lst = []
    while l_ptr < c and r_ptr < r:
        if lst[l_ptr] < lst[r_ptr]:
            tmp_lst.append(lst[l_ptr])
            l_ptr += 1
            continue
        else:
            tmp_lst.append(lst[r_ptr])
            r_ptr += 1

    while l_ptr < c:
        tmp_lst.append(lst[l_ptr])
        l_ptr += 1

    while r_ptr < r:
        tmp_lst.append(lst[r_ptr])
        r_ptr += 1

    for tmp_i, i in enumerate(range(l, r)):
        lst[i] = tmp_lst[tmp_i]

    return lst

if __name__=='__main__':
    T = int(input())

    for t in range(1, T + 1):
        N = int(input())
        lst = list(map(int, input().split()))

        merge_sort(lst, 0, len(lst))

        print('#{}'.format(t), end=' ')
        print(*lst, sep=' ')

T = 10

for t in range(1, T+1):
    int(input())
    MAP = [[0 for _ in range(102)] for _ in range(100)]
    for i in range(100):
        MAP[i][1:-1] = map(int, input().split())

    start_j = 0
    for j in range(1, 101):
        if MAP[99][j] == 2:
            start_j = j
            break

    i = 99
    j = start_j
    while i:
        if MAP[i][j + 1]:
            while MAP[i][j + 1]:
                j += 1
            i -= 1
        elif MAP[i][j - 1]:
            while MAP[i][j - 1]:
                j -= 1
            i -= 1
        else:
            i -= 1

    result = j - 1
    print('#{} {}'.format(t, result))

T = int(input())

for t in range(1, T+1):
    N, M = map(int, input().split())
    MAP = []
    for i in range(N):
        MAP.append(list(map(int, input().split())))

    total_map = [[0 for _ in range(N + 1)] for _ in range(N + 1)]

    for i in range(1, N + 1):
        for j in range(1, N + 1):
            total_map[i][j] = MAP[i - 1][j - 1] + total_map[i - 1][j] + total_map[i][j - 1] - total_map[i - 1][j - 1]

    result = total_map[M][M]
    for i in range(M, N + 1):
        for j in range(M, N + 1):
            total = total_map[i][j] - total_map[i - M][j] - total_map[i][j - M] + total_map[i - M][j - M]
            if total > result:
                result = total

    print('#{} {}'.format(t, result))

T = 10

for t in range(1, T+1):
    lst = []
    _ = int(input())
    for i in range(100):
        lst.append(list(map(int, input().split())))

    max = 0
    for i in range(100):
        max += lst[0][i]


    for i in range(100):
        total = 0
        for j in range(100):
            total += lst[i][j]
        if max < total:
            max = total

    for j in range(100):
        total = 0
        for i in range(100):
            total += lst[i][j]
        if max < total:
            max = total

    total = 0
    for i in range(100):
        total += lst[i][i]

    if max < total:
        max = total

    total = 0
    for i in range(100):
        total += lst[99 - i][i]

    if max < total:
        max = total

    print('#{} {}'.format(t, max))

T = int(input())

di = [0, 1, 0, -1]
dj = [1, 0, -1, 0]

for t in range(1, T+1):
    n = int(input())

    lst = [[0 for _ in range(n+2)] for _ in range(n+2)]

    for i in range(1, n+2):
        lst[0][i] = -1
        lst[n + 1][i] = -1
        lst[i][0] = -1
        lst[i][n + 1] = -1

    i = 1
    j = 0
    num = 1
    d = 0
    while num <= n*n:
        next_i = i + di[d]
        next_j = j + dj[d]

        if lst[next_i][next_j]:
            d = (d + 1) % 4
            continue

        i = next_i
        j = next_j
        lst[i][j] = num
        num += 1

    print('#{}'.format(t))
    for i in range(1, n+1):
        print(*lst[i][1:n+1], sep=' ')