Every once in a while, Mishka Jabereen sends an interesting mathematical puzzle to his friends. This week’s puzzle will be about so-called “repetitive” numbers – the ones whose decimal expansion has just one kind of digit in it. (Examples of such numbers include 7, 11, and 5555.) The puzzle is about finding the largest repetitive number subject to two additional restrictions:
A concrete example of such a problem statement would be: Find the largest repetitive number with at most 47 digits, which is divisible by 42 or 47! Mishka is currently playing around with a few such problem statements and he’d like to know all the answers, so that he can choose the nicest one.
Problem specification
A puzzle is described by a number K, the maximal number of digits allowed in the repetitive number, and a set of numbers d1, d2, …, dR. Your task is to find the greatest repetitive number X that has at most K digits when written in decimal notation, and it is divisible by at least one of the di.
Input specification
The first line of the input file contains an integer T specifying the number of test cases. Each test case is preceded by a blank line.
Each test case starts with a line containing the numbers K and R. The next R lines contain the numbers di.
Output specification
We can describe a repetitive number by specifying its number of digits N and the digit D it contains.
For each test case, the output shall contain one line containing two integers N and D that describe the largest repetitive number that satisfies the conditions from the problem statement.
Example
| input
3
47 2 42 47 99 4 123 234 345 456 3 1 4700 |
| output
46 9
96 6 1 0 Note that in the third test case “3 0” would not be a correct answer, as “000” is not a valid integer. |