Joining Byte Blocks
As you are probably aware, the Internet protocols specify a canonical byte order convention for data transmitted over the network called network byte order, so that machines with different byte order conventions can communicate. But what if such canonical byte order didn't exist? We would probably be trapped in chaos trying to figure out the byte order for every machine we want to communicate with. But luckily, no matter the byte order (big-endian or little-endian), there will be byte blocks that will always be read correctly.
Imagine you have a list of byte blocks. In order to minimize the number of trasmission operations required to send all of them, you want to pair as many as possible blocks. Note that the resulting byte frame should have same representation in both network orders, i.e., they should be a palindrome when paired. The rules for such pairings are the following:
- No block can be paired with itself.
- A block can be paired zero or one time.
- You cannot pair more than two blocks.
For the ease of representation we will use lowercase latin characters to represent byte blocks. Suppose we have two blocks and , and they are paired to form the frame , then it has the same representation in any of the byte order.
Now, given the list of blocks, using the pairings described above, what's the minimum number of transmissions required to send them all?
Note: A block can either be transmitted alone, or paired with another block (if the pair satisfies above criteria).
Input Format
There will be multiple test cases per input file. Every test case will start with a number telling you the size of the list. Then lines follow, each one with a block, where each byte has been replaced by its current English alphabet lowercase letter. No test case will have more than potential pairs.
Output Format
Output a single line per test case in the input with the required answer.
Constraints
- Each block consisits of lowercase latin characters, .
Sample Input
6
aaababa
aa
ababaaa
baaa
a
b
9
aabbaabb
bbaabbaa
aa
bb
a
bbaa
bba
bab
ab
Sample Output
3
5
Explanation
Sample Case #00: All of the blocks can be paired into following frames.
- "baaa" + "b" = "baaab"
- "aaababa + "ababaaa" = "aaababaababaaa"
- "aa" + "a" = "aaa"
Sample Case #01: Following frames will be sent
- "aabbaabb" + "bbaabbaa" = "aabbaabbbbaabbaa"
- "aa" + "a = "aaa"
- "bba" + "bb" = "bbabb"
- "bab" + "ab" = "babab"
- "bbaa"
Tested by: Piotr Gajowiak / Paweł Kacprzak