You are a given a simple task to find the minimum positive integer x such that x is a multiple of N and it doesn't contains any of the forbidden digits.

Input
First line contains T denoting the number of test cases.
First Line of every test case gives you the integer N (explained in the problem statement).
Next line contains space seperated list of forbidden digits.

Output
If there is no solution print "Naa Ho Paayega" on a single line.
If there is a solution and the number of digits in the number are strictly less than 9 then print the number on a single line.
Otherwise, print a string of the form abc...def on the 1st line where abc are the first 3 digits of the found solution and def are the last 3 digits of the same.On the second line print the number of digits in this found solution.

Constraints
T<=100
1<=N<=10000

Sample Input

3
8
2 3 4 5 6 7 8 9
9
1 3 4 5 6 7 8 9
10000
0

Sample Output

1000
222...222
9
Naa Ho Paayega

Problem Setter : Arjun Singh Bhatia
Problem Tester : Shikhar Sharad

Languages: AWK,Bash,Brain,C#,JavaScript,Pascal,Perl,PHP,Python,Python3,Ruby,Text

Time Limit: 3 Second(s)
Score: 100 Point(s)
Input File Limit: 50000 Bytes

Mode Judge

RankNameScore
1xyz0
2Ams0
3TIP0
4team420
5xyzz0
6asdasdasd0
7abcd0
8khankhan0
9Gabriel0
10gigel0