You are given four strings, each consisting of at most 50 lower case letters ('a'-'z'). Count the number of non-empty common subsequences of them (the number of distinct non-empty strings which are subsequences of all four strings). Note that a subsequence does not have to be contiguous.

Input

Four lines: each line consists of a single string.

Output

An integer representing the answer.

Example

Input:
aabb
abab
baba
acba

Output:
4

The four sequences are "a", "b", "aa", and "ab".