Sum of All Root-to-Leaf Paths

You are given a rooted binary tree where each node contains an integer value. A root-to-leaf path forms a number by concatenating the values along that path. For example, if a path is 1 → 2 → 3, then the number formed is \(123\). Your task is to compute the sum of all such numbers for every root-to-leaf path in the tree.

The input consists of multiple test cases. In each test case, the tree is described by edges. Each edge specifies a parent node, a child node, and a direction character ('L' for left, 'R' for right). It is guaranteed that the root of the tree has the value 1.

Example: For a tree with 5 nodes and the following edges:

1 2 L
1 3 R
2 4 L
2 5 R

There are three root-to-leaf paths: 1→2→4, 1→2→5, and 1→3. The numbers formed are 124, 125, and 13 respectively, so the output is \(124 + 125 + 13 = 262\).

inputFormat

The input begins with an integer \(T\), the number of test cases. For each test case:

1. The first line contains an integer \(N\) (the number of nodes in the tree).
2. The next \(N-1\) lines each contain two integers and a character, representing an edge in the tree: the parent node, the child node, and the direction (either 'L' or 'R').

It is guaranteed that the tree is rooted at node 1.

outputFormat

For each test case, output a single line containing the sum of all the numbers formed by root-to-leaf paths.

## sample

5
3
1 2 L
2 3 L
5
1 2 L
1 3 R
2 4 L
2 5 R
4
1 2 L
2 3 L
3 4 L
4
1 2 R
2 3 R
3 4 R
7
1 2 L
1 3 R
2 4 L
2 5 R
3 6 L
3 7 R

123
262
1234
1234
522

</p>