Problem D: Tree Number

## Problem D: Tree Number

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 717  Solved: 262
[Submit][Status][Web Board]

## Description

Given the order of a tree's pre-order traversal and post-order traversal, you are asked to find out how many distinct binary trees fit the given traversal orders.

## Input

The first line contains one integer $$T$$, which denotes the number of the test cases $$(1\le T\le 10\ 000)$$. The nodes of a binary tree are represented by capital letters, and no two distinct nodes are represented with the same letter.

In each case, the first line contains a string $$S_{pre}$$, denoting the access order of the pre-order traversal. The second line contains a string $$S_{post}$$, denoting the access order of the post-order traversal $$(|S_{pre}|, |S_{post}|\le 26)$$.

## Output

Output the number of binary trees which meet the requirements.

## Sample Input

1
ABCD
DCBA

## Sample Output

8

[Submit][Status]