spoj#THECODE. Subset with all Digits

Subset with all Digits

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}