[Login|Register]
Problems

Status

Rank

Problem 1301
Common sub-sequence
Time Limit: 1000ms
Memory Limit: 65536kb
Description
A 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.
Input
The 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.
Output
Output the answer of each case.
Sample Input
2
1 1 1
11 11 11
Sample Output
1
2
University of Science and Technology of China
Online Judge for ACM/ICPC
Processed in 1.1ms with 1 query(s).