There are eight planets and one planetoid in the Solar system. It is not a well known fact that there is a secret planet S4 inhabited by small creatures similar to bears, their codename being Lodas. Although this fact is well hidden from the public, the association Savez sent a team lead by general Henrik to study the Lodas. It has been discovered that Lodas have the ability of teleportation and he wants to hire them in his army.
One Lod consists of N strings where the ith string is denoted by xi. Research has shown that the number of teleportations a Loda can make depends on one special subsequence (not necessarily consecutive) of these strings. Strings xi and xj (i < j) can both be in that sequence if and only if string xj both starts with and ends with string xi. The number of teleportations a Loda can make is the length of the longest described subsequence.
Determine the number of teleportations.
입력 input input input 5 A B AA BBB AAA 5 A ABA BBB ABABA AAAAAB 6 A B A B A B output output output 3 3 3 Clarification of the first example: Prefix and suffix can intersect so subsequence is A → AA → AAA Clarification of the third example: Strings in the subsequence are allowed to be equal so subsequence is A → A → A or B → B → B
출처:coci/2015-2016/contest2 4/6