A subsequence of a string is obtained by removing zero or more characters from it. You are given three strings, and must determine the number of different non-empty subsequences they all share.

For example, in sample 1 the 6 subsequences common to all of the strings are: "c", "a", "l", "al", "ca" and "cl".

Input

Each test case consists of three words that are given in three separate lines. The length of each word in no more than 50. Every word contains only lowercase letters ('a'-'z').

Output

For each test case print the number of different non-empty subsequences three words all share.