Left recursion
In the study of formal grammars and automata (TFGA), context-free grammars (CFGs) are essential. A CFG is defined by a four-part structure: a set N of non-terminal symbols, a set T of terminal symbols, a set P of production rules, and a start symbol S from N.
Each production rule p in P is expressed as A→α, where A is a non-terminal symbol (A ∈ N), and α is a sequence of terminal and non-terminal symbols. The derivation of a word begins with a string containing only the start symbol S. At each step, one non-terminal symbol in the current string is replaced by the right-hand side of a production where it appears on the left. The process concludes when the string consists solely of terminal symbols.
In theoretical contexts, it's often useful to convert grammars into specific forms, known as normal forms. This conversion typically starts by removing left recursion. In this task, we focus on a specific type called immediate left recursion. A production A→α exhibits immediate left recursion if the first symbol of α is A.
Given a CFG, determine how many rules exhibit immediate left recursion.
Input
The first line of the input contains the number n (1 ≤ n ≤ 1000) of rules in the grammar. Each of the next n lines contains one rule. Non-terminal symbols are represented by uppercase Latin letters, and terminal symbols by lowercase letters. The left side of the production is separated from the right side by the symbol ->. The right side of the production is always non-empty and has a maximum length of 30 symbols.
Output
Output the number of rules that contain immediate left recursion.