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}