Once upon a time, many many eons ago lived a very clever emperor Marian. After conquering all the known and a little part of unknown land, his life has become a little boring. So he tried to solve unsolvable problems, prove unprovable theorems and many others things with un in front of it. But, in the meantime he studied his favorite palindromes. A palindrome is a word, phrase, number or any other sequence of units (like a strand of DNA) which has the property of reading the same in either direction (as Wikipedia says). No wonder he was so fascinated. Soon enough he solved many problems involving palindromes. He wanted to share his wisdom with others, but nobody else could solve same problems like he did (even when he was giving beer and chocolate as reward). Marian became unhappy. So one of his friends tried to think of a new problem for Marian to solve. One evening, while sitting in his cottage, an idea came to his mind. He remembered, that he had many old newspapers with him. So he took scissors and cut newspapers to rectangles of random sizes. Then he wrote down all lowercase characters, from every piece of paper to one line. So he got many lines with some words. "Let every line be a new symbol defined by a string of lowercase chars." he said. "This new set containing tousands of symbols may please good ol' friend of mine. He can build palindromes from it for the rest of his life." But now he sits puzzled and tries to count how many different symbols are in this set and also how big palindrome can be build using those symbols. Help him for he is not very good mathematician nor programmer.
Task
Let A be a symbol of our set defined by string of upmost 50 english characters. Symbols A and B are same when strings defining both of them are exactly the same. So 'aaabba' and 'aaabba' are the same symbols while 'aaabba' and 'aaabb' are not.
Count how many different symbols are in the input file and what is the maximal length of palindrome that can be build from those symbols.
Beware: You can use one symbol up to as many times as it is in the input.
Input
First line of input contains N, 0 < N < 200000, number of following lines. Every line contains one symbol defined as up to 50 lowercase english characters (from 'a' to 'z').
Output
Output one line containing X and Y, where X is the number of different symbols and Y is the length of the longest palindrome.
Example 1
Input:
5
aaabc
abc
aaabc
a
abc
Output:
3 5
Explanation:
Palindrome will be: 'aaabc' 'abc' 'a' 'abc' 'aaabc' or
'abc' 'aaabc' 'a' 'aaabc' 'abc'. There are no other possible palindromes with the same size.
Example 2
Input:
5
a
ab
abc
abcd
abcde
Output:
5 1
Explanation:
Palindrome will be just one of the characters.
Problem by Samuel BWPOW Kupka
| 
Stredná