DELCOMM2 - DEL Command II

no tags 

It is required to find out what's the maximum number of files that can be deleted from MS-DOS directory executing the DEL command of MS-DOS operation system only once. There are no nested subdirectories.

Note

DEL command has the following format: DEL wildcard

The actual wildcard as well as a full file name can be made up of a name containing 1 up to 8 case-sensitive characters. In a wildcard the characters '?' and '*' can be used. A question mark substitutes exactly one character of the full file name, an asterisk any sequence of characters even empty one.

MS-DOS system can permit maybe other wildcards but they can not be used in this task. File names consist only of Latin letters and digits.

Input

The first line of the input is an integer M, then a blank line followed by M datasets. There is a blank line between datasets.

Input data for each dataset contains a list of full file names without any extra empty lines and spaces. Each name is written in a separate line of input data file and ended with a control sign: '+' for delete or '-' for keep. Full file names are not repeated. The list comprises at least one file, and at least one file is marked to be deleted. There are no more than 250 files.

Output

For each dataset, write to the first line of output the maximum number of files one DEL command can delete.

Example

Input:
2

BP +
BPC +
TURBO -

EXCHANGE +
EXT +
HARDWARE +
MOUSE –
NETWORK –

Output:
2
2
Hint:

For the two tests above, the corresponding DEL commands are DEL BP* and DEL EX*.

Link

You can try problem DELCOMM first. It's far easier than this problem.


hide comments
:D: 2012-11-22 07:10:13

"No extra" doesn't mean none. Apart from that, you can implementing reading both versions. That approach will save you a world of hurt in various problems.

It was never said "*" can only be at the last position.

Last edit: 2012-11-22 18:05:48
Marko: 2012-05-14 21:24:31

And, can asterisk '*' only appear at the last position of the wildcard?

Marko: 2012-05-14 20:40:10

"Input data for each dataset contains a list of full file names without any extra empty lines and spaces. Each name is written in a separate line of input data file and ended with a control sign: '+' for delete or '-' for keep."

so why did you put spaces in example? what is correct input "BP +" or "BP+"?


Added by:Fudan University Problem Setters
Date:2007-04-01
Time limit:10s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: C99 ERL JS-RHINO
Resource:Chinese National Olympiad in Informatics 1997,Day 1