Description

A substring of a string is a contiguous block of characters. For example, for the string aabbcc, aa and abbc are substrings, while abc and aba are not. Now, given three strings, how many distinct substrings do all three of them contain in common (excluding the empty string)?

Note: Even if the same common substring appears at different positions, it still counts as 1 kind only. See the example.

Input Format

Each test case consists of 3 lines. Each line is a string containing only lowercase letters.

Output Format

Output the number of distinct substrings common to the 3 strings.

apartment
apache
approach

6

Hint

The substrings common to the 3 strings are: "a", "p", "ap", "pa", "aa", "apa". Among them, the substring "a" occurs multiple times, but since we count kinds of common substrings, "a" counts as only 1 kind.

In 100% of the testdata, the length of each string does not exceed 100. Each string contains only lowercase letters.

Translated by ChatGPT 5