슈퍼 2048 (스몰)

2048은 격자 위의 타일을 밀어서 같은 수끼리 합치고, 마지막에 2048이 적힌 타일을 만드는 1인용 게임이다.

원래 2048은 4 x 4 격자에서 진행한다. 한 번의 이동에서 플레이어는 왼쪽, 오른쪽, 위, 아래 중 한 방향을 고르고, 모든 타일을 그 방향으로 갈 수 있는 데까지 동시에 민다. 이동 중에 같은 수가 적힌 타일 두 개가 부딪히면 두 수를 더한 값이 적힌 타일 하나로 합쳐진다. 한 번의 이동에서 새로 만들어진 타일은 다시 합쳐지지 않으며, 합치기는 이동 방향에서 앞쪽에 있는 타일부터 먼저 일어난다. 예를 들어 한 줄에 2가 세 개 "2 2 2"로 놓인 상태에서 왼쪽으로 밀면 "4 2 0"이 된다. 앞쪽에 있는 2 두 개가 먼저 합쳐진다.

위 그림은 모든 타일을 오른쪽으로 밀었을 때 4 x 4 격자가 어떻게 바뀌는지 보여 준다.

앨리스와 밥은 이 게임을 우연히 발견했고 타일이 합쳐지는 느낌을 좋아하게 됐다. 몇 판을 하고 나니 판이 작다고 느껴서 크기를 N x N으로 늘렸고, 이렇게 커진 게임을 "Super 2048"이라고 부른다.

판이 커지자 결과를 눈으로 따라가기 어려워졌다. 주어진 판에서 모든 타일을 지정된 방향으로 한 번 밀었을 때 판이 어떤 모습이 되는지 계산하는 프로그램을 작성하라.

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스의 첫째 줄에는 판의 한 변의 길이 N과 타일을 밀 방향 DIR이 공백 하나로 구분되어 주어진다. DIR은 "left", "right", "up", "down" 중 하나다.

다음 N개 줄에는 판의 처음 상태가 주어진다. 각 줄에는 공백으로 구분된 정수 N개가 있고, 각 줄은 판의 한 행을 위에서 아래 순서로 나타낸다. 각 정수는 그 칸에 놓인 타일의 값이며, 빈 칸은 0이다.

제한

• 1 ≤ T ≤ 20
• 1 ≤ N ≤ 10
• 판의 각 수는 0이거나 2 이상 1024 이하의 2의 거듭제곱이다.

각 테스트 케이스마다 첫 줄에 "Case #x:"를 출력한다. x는 1부터 시작하는 테스트 케이스 번호다. 그 다음 N개 줄에 걸쳐 이동이 끝난 뒤의 판을 입력과 같은 형식으로 출력한다. 각 줄에는 공백으로 구분된 정수 N개를 쓴다.