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

  1. Challenge Walkthrough
    Let's walk through this sample challenge and explore the features of the code editor.1 of 6
  2. Review the problem statement
    Each challenge has a problem statement that includes sample inputs and outputs. Some challenges include additional information to help you out.2 of 6
  3. Choose a language
    Select the language you wish to use to solve this challenge.3 of 6
  4. Enter your code
    Code your solution in our custom editor or code in your own environment and upload your solution as a file.4 of 6
  5. Test your code
    You can compile your code and test it for errors and accuracy before submitting.5 of 6
  6. Submit to see results
    When you're ready, submit your solution! Remember, you can go back and refine your code anytime.6 of 6
  1. Check your score