슈퍼 2048 (라지)

2048은 4 x 4 격자에서 혼자 하는 게임이다. 한 번 움직일 때마다 모든 타일이 왼쪽, 오른쪽, 위쪽, 아래쪽 중 한 방향으로 갈 수 있는 데까지 미끄러진다. 움직이는 동안 같은 수가 적힌 타일 두 개가 부딪히면 두 수를 더한 값이 적힌 타일 하나로 합쳐진다.

같은 수가 세 개 이상 나란히 있을 때는 두 규칙이 결과를 정한다. 합쳐져서 새로 생긴 타일은 같은 이동에서 다시 합쳐지지 않고, 타일은 이동 방향으로 가장 가까이 있는 타일과 먼저 합쳐진다. 예를 들어 한 줄이 2 2 2인 상태에서 왼쪽으로 밀면 4 2 0이 된다. 왼쪽의 두 타일이 먼저 합쳐지고, 새로 생긴 4는 그대로 남는다.

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

앨리스와 밥은 4 x 4 판이 지겨워져서 판을 N x N으로 넓혔고, 이 게임을 슈퍼 2048이라고 부른다. 판이 커지자 결과를 눈으로 따라가기 어려워졌다. 판 하나와 방향 하나가 주어질 때, 모든 타일을 그 방향으로 민 뒤의 판을 구하는 프로그램을 작성하라.

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

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

제한

• $1 \le T \le 100$
• $1 \le N \le 20$
• 판에 적힌 수는 0이거나 2 이상 1024 이하의 2의 거듭제곱이다.

각 테스트 케이스마다 첫 줄에 Case #x:를 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이다. 이어서 $N$개 줄에 타일을 민 뒤의 판을 입력과 같은 형식으로, 한 줄에 $N$개씩 공백으로 구분해 출력한다.