THECODE - 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 test cases.

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}


Added by:Kriti Joshi
Date:2019-07-14
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All

hide comments
2023-08-21 19:58:20 Rafail Loizou
@tech_addict Not to spoil anything but it would be good to add the DP tag. Many people search problems by their tags. If you think this spoils the answer then just delete my comments. IMO it doesn't that's why I wrote the comment.
2020-06-24 14:41:17
is it possible that two numbers are same?
2019-08-24 16:14:00
any can you please give me few test cases?
2019-07-15 00:58:35
I don't know how to solve this optimally, but I've tried what I could and got AC. Thanks for setting the constraints that make it possible, will probably learn a lot from this. Appears to be a rare concept for a SPOJ problem to be based on.

BTW. A general tag exists: https://www.spoj.com/problems/tag/set-cover , please change if it's possible.

Last edit: 2019-07-15 01:02:00
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.