SSHUFFLE  String Shuffle
Given three strings consisting of just lowercase letters, count the number of ways that the third string can be constructed by combining two subsequences from the first two strings.
One derives a subsequence of the string by deleting zero or more characters from a string. For example, “”, “a”, “b”, “c”, “ab”, “ac”, “bc”, and “abc” are all the subsequence strings of “abc”. (Note that the empty string, “”, is a subsequence of any string.)The two subsequences are combined to make a third string by shuffling them together. That is, the relative order of the letters from the subsequence cannot be changed in the target string; but the two subsequences can be interleaved arbitrarily. For example, consider the two subsequences “abc” and “de”. By combining them, one can get the following strings: “abcde”, “abdce”, “abdec”, “adbce”, “adbec”, “adebc”, “dabce”, “dabec”, “daebc”, and “deabc”.
Input
The first line of the input contains a single integer t that indicates the number of test cases. Each test case contains 3 strings, each containing only lowercase characters. The length of each string is between 1 and 60, inclusive.
Output
For each test case, output a line with a single integer that denotes the number of ways that one can construct the third string from the first two strings as described above.
Example
Input: 3 abc abc abc aa aa aa abbcd bccde abcde Output: 8 10 18
hide comments
kira28:
20170107 18:54:56
Done with a 3D DP


Alex Gu:
20151228 20:12:12
the answer should not fit in int, but if use int, then you will get AC 

Amruth Kumar Juturu:
20150114 06:26:46
Can anyone please give some testcases? Status of my submission shows wrong answer. 
Added by:  Daniel Gómez Didier 
Date:  20081118 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO NODEJS PERL6 VB.NET 
Resource:  2008 PUJ  Circuito de Maratones ACIS / REDIS 