Submit: 717 Solved: 262

[Submit][Status][Web Board]

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.

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)\).

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 the number of binary trees which meet the requirements.

```
1
ABCD
DCBA
```

`8`