Time Limit: 1000ms
Memory Limit: 65536kb
DescriptionA new sequence after removing 0 or more characters sequentially from original sequence is called sub-sequence of original sequence.
For example: "0123" is the sub-sequence of "2011123", while it is not the sub-sequence of "2111023".
Given three sequences composed of characters '0' to '9', can you count the number of non-empty common sub-sequence of them?
Notice: same sub-sequence should be counted only once.
InputThe input consists of multiple test cases.
The first line, an integer T (1<=T<=100), indicates the number of cases. Each test case has only one line, containing three sequences whose length is at most 40.
OutputOutput the answer of each case.
2 1 1 1 11 11 11