CSUBSEQS - Common Subsequences


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".



Added by:Bin Jin
Date:2008-06-22
Time limit:0.522s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: CPP
Resource:co-author: Neal Wu