EllysKeys

The old-fashioned door lock keys are usually some pattern of cuts into a metal that should fit perfectly into the lock in order to unlock it. The key also has a handle at one of the ends which is used to turn the key after it is inserted into the lock.

The simplest keys have all the cuts at an equal depth. On such keys, each part of the key is either cut or not. We can represent such keys using strings of two characters: a period ('.') will represent a cut piece and a caret ('^') will represent an uncut piece (also called a "tooth").

An example key would be ".^^.^.^^^.^.^". This key has length 13 and has five cuts (at zero-indexed positions 0, 3, 5, 9, and 11) and eight teeth.

Elly is designing a new lock mechanism. Her lock will be opened by using multiple simple keys (as described above). The keys will be inserted parallel to each other and aligned so that they all end at the same depth.

The more simple keys the girl uses, the better the security of the lock gets. However, due to the specifics of the lock, no two keys can have a tooth at the same position.

For example if the girl has the following keys:

    { "..^.^^.^", 
      "^.^^...^", 
      "^.....^." }

she can use two of them: if she places "..^.^^.^" and "^.....^." next to each other, at most one of them has a tooth at each position. She cannot use all three keys, because there would be multiple teeth at zero-indexed positions 0, 2, and 7. Moreover, the girl cannot even use only the keys "^.^^...^" and "^.....^." together, because they have a tooth at the same position.

The girl has a collection of keys she can use for her new locking system. They are given to you in the String[] keys. Each element of keys represents a single key in the format described above ('.' for a cut and '^' for a tooth).

Help Elly: Determine and return the maximal number of keys she can use for her lock.