## 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 acbaOutput: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 |