407753: GYM102890 D Debugging the network

A communication string is defined as a string containing only lowercase letters from the English alphabet ('a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z'). In order to make easier and cheaper to send these strings over slow networks a compression method has been defined as follow: If a substring in the string with length of at least $$$2$$$ characters consists only of occurrences of the same letter, then, replace the substring with its length followed by the letter, this is done always in a way that no two consecutive positions of the string have the same letter. For example, the string aaaaabbc would be replaced with the string 5a2bc. The communication string is compressed before sending the message over the network, then a system receiving the message will decompress the string before the communication is acknowledged to be successful.

After years of this compression method working as expected suddenly some systems in the network started to break, some debugging in the system showed it breaks when the communication string is longer than $$$K$$$ characters.

Your task is to determine if the system in the network will not break while uncompressing a compressed string given the compressed string, and the value $$$K$$$.

The first line of input contains a single integer $$$T$$$ ($$$1 \leq T \leq 100$$$), representing the number of test cases. Each of the next $$$T$$$ lines contain a string $$$S$$$ ($$$1 \leq |S| \leq 1000$$$) and a number $$$K$$$ ($$$1 \leq K \leq 10^6$$$) separated by a space, representing, respectively, the compressed string and the longest communication string length that is able to be transmitted over the network.

For each test case in the input print a line containing the communication string if the given compressed string is safe to be uncompressed, otherwise print a line with the string "unfeasible".

4
5a2bc 8
5a2bc 7
asdf4x 50
asjkdf10000000000kz 1000000

aaaaabbc
unfeasible
asdfxxxx
unfeasible