Bytie's Display

Byteman gave his son Bytie a display for his third birthday. The display is a row of elements, and each element is built from seven segments.

A single element. The long hexagons are the segments.

By switching individual segments on or off, an element can show a digit, as illustrated below. Any other combination of lit segments does not represent a digit.

The digits 0 to 9. Black segments are on, white segments are off.

Bytie asks: what is the largest number the display can show if you are allowed to

• swap any two elements as many times as you like, and
• switch at most $n$ segments on or off in total?

At the end the display must show a valid number (it need not be valid at intermediate steps), and you may only swap whole elements. Help Byteman solve the riddle.

The first line contains an integer $k$ ($1 \le k \le 50$), the number of test cases. Each of the next $k$ lines describes one test case with three integers $n$, $l$, $a$ ($0 \le n \le 200000$, $1 \le l \le 100000$): $n$ is the maximum number of segment switches you may perform, and $a$ is the current state of the display written as exactly $l$ digits (leading zeros are allowed).

For each test case, print one line: an integer that is exactly $l$ digits long (leading zeros allowed), equal to the largest number that can be obtained under the rules.

Suppose the display shows 10 and one switch is allowed. First swap the two elements to get 01, then turn on the middle horizontal segment of the left element so that the 0 becomes an 8. The display then shows 81, which is the largest number obtainable.

The initial state, and the state after the swap and after turning on the middle horizontal segment.