Yesterday, I had a coding interview and got this problem, which while doing using brute force all the test cases are not passing.

Given a paragraph P of words which contain some PAN card Numbers. Count the number of distinct valid PAN card numbers in P.

A valid PAN card number is a 10 length alphanumeric word of the form: "AAAAA1111A"

A denotes any letter of English uppercase alphabet.

1 denotes any digit in 0,1,2.....9.

The fourth character can be only from the set {"A","B","C","F","G","H","L","J","P","T","K"}.

The fifth character must be same as the first character.

Input

$MKOFM53365d*02Hd|  ^BAAAB0000CAAC1111...%G

Output
2

Constraint: 1 < | P | <= 10^6