Jasio

Time limit1sMemory limit128 MB

Summary

Count words that contain a palindrome substring of length at least 2, both literally and with i=j and p=b=d treated as equal.

Level: Easy3 of 10
Topics: String, Implementation, Brute force
Solved: No attempts yet

Problem

Jasio has a list of words. He wants to count how many of them contain a palindrome of length at least two as a substring.

A palindrome reads the same forwards and backwards. For example, ala is a palindrome, but kot is not, because reversed it reads tok. The word foo contains the palindrome oo (length at least two), while the word ftof contains no palindrome of length at least two.

There is a catch. Jasio cannot read well yet: he cannot tell the letter i from j, and he cannot tell the letters p, b, and d apart. So when he reads a word he treats i and j as the same letter, and treats p, b, and d as the same letter. Because of this, Jasio also considers the word pod to contain a palindrome: to him p and d look the same, so pod reads the same both ways.

Write a program that:

reads the list of words to process,
counts the words that, read literally, contain a palindrome of length at least two,
counts the words that Jasio would consider to contain a palindrome of length at least two, treating i and j as one letter and p, b, d as one letter,
prints both counts.

Input

The first line contains the number of words $n$ ( $1 \le n \le 10000$ ). Each of the next $n$ lines contains exactly one word. Words consist only of lowercase English letters, and no word is longer than 200 characters.

Output

Print exactly two lines, each containing a single integer. The first line is the number of words that contain a palindrome of length at least two. The second line is that same count under Jasio's rule (i = j, p = b = d).

Examples3

Example 1
Input
```
4
foo
bar
ala
pod
```
Expected output
```
2
3
```
Example 2
Input
```
1
kot
```
Expected output
```
0
0
```
Example 3
Input
```
1
aa
```
Expected output
```
1
1
```