바이티의 디스플레이

바이트만은 세 번째 생일을 맞은 아들 바이티에게 디스플레이를 선물했다. 이 디스플레이는 한 줄로 늘어선 소자들로 이루어지며, 각 소자는 일곱 개의 획으로 구성된다.

소자 하나의 모습. 길쭉한 육각형이 각각의 획이다.

각 획을 켜거나 꺼서 아래 그림처럼 소자에 숫자를 나타낼 수 있다. 그 밖의 조합은 어떤 숫자도 나타내지 않는다.

0부터 9까지의 숫자. 검은 획은 켜진 상태, 흰 획은 꺼진 상태를 뜻한다.

바이티가 문제를 냈다. 다음 두 가지가 허용될 때 디스플레이에 나타낼 수 있는 가장 큰 수는 무엇일까?

• 임의의 두 소자를 원하는 만큼 여러 번 맞바꾼다.
• 획을 켜거나 끄는 조작을 통틀어 최대 $n$번 한다.

마지막에는 디스플레이가 올바른 수를 나타내야 한다(중간 과정에서는 그렇지 않아도 된다). 또한 소자는 통째로만 맞바꿀 수 있다. 바이트만이 이 수수께끼를 풀 수 있도록 도와주자.

첫 줄에 테스트 케이스의 수를 나타내는 정수 $k$ ($1 \le k \le 50$)가 주어진다. 이어지는 $k$개의 줄에는 각각 한 테스트 케이스가 세 정수 $n$, $l$, $a$ ($0 \le n \le 200000$, $1 \le l \le 100000$)로 주어진다. $n$은 획을 켜거나 끄는 조작을 할 수 있는 최대 횟수이고, $a$는 현재 디스플레이 상태를 정확히 $l$자리의 숫자로 나타낸 것이다(맨 앞의 0도 허용된다).

각 테스트 케이스마다 규칙에 따라 얻을 수 있는 가장 큰 수를 정확히 $l$자리(맨 앞의 0 허용)의 정수로 한 줄에 출력한다.

디스플레이에 10이 표시되어 있고 조작을 한 번 할 수 있다고 하자. 먼저 두 소자를 맞바꿔 01을 만든 뒤, 왼쪽 소자의 가운데 가로 획을 켜서 0을 8로 바꾼다. 그러면 디스플레이에는 81이 나타나며, 이것이 얻을 수 있는 가장 큰 수이다.

처음 상태와, 소자를 맞바꾸고 가운데 가로 획을 켠 뒤의 상태.