As we all know, Harry Porter learns magic at Hogwarts School. However, learning magical knowledge alone is insufficient to become a great magician. Sometimes, Harry also has to gain knowledge from other certain subjects, such as language, mathematics, English, and even algorithm.
Today, Harry is on his biological class, his teacher is doing experiment with DNA right now. But the clever teacher faces a difficult problem. He has lots of genes. Every time he picks gene a and gene b. If he want to connect gene a and gene b, he should calculate the length of longest part that the gene a’s suffix and gene b’s prefix can overlap together. For example gene a is "AAT" and gene b is "ATT", then the longest common part is "AT", so the answer is 2. And can you solve this difficult problem for him?