Given a list of n d-digit numbers, choose the smallest subset from the list that covers all the digits [0 - 9]. 

Input

First line contains a positive integer T representing number of testcases.

Next line contains two numbers n and d, where n is the size of the list and d is number of digits in each number.

Next n lines follow each containing a d digit number made from [0 - 9]

1 ≤ t ≤ 100

1 ≤ n ≤ 1000

1 ≤ d ≤ 1000

Output

Output the length of the smallest subset that covers all digits [0 - 9]. Return -1 if not possible.

Example

Input:
2
4 5
01234
56789
01456
13452
4 5
11234
56789
01456
13452
Output:
2
3

Explanation

Smallest set will be {01234, 56789}

Smallest set will be {11234, 56789, 01456}