Given a positive integer N (1 <= N <= 10000) and some digits, find the smallest positive multiple of N whose decimal notation does not contain any of the given digits.

Input

Each test case contains two lines. The first line contains two integers N and m separated by a single space. The second line contains m digits separated by spaces. Input terminates by EOF.

Output

For each test case output its case number (starting from 1) and the answer in a single line, or "-1" (without quotes) if the answer doesn't exist.

Example

Input:
2345 3
7 8 9
100 1
0
Output:
Case 1: 2345
Case 2: -1