In an infinite binary tree:
A walk on the binary tree starts in the root. Each step in the walk is either a jump onto the left child, onto the right child, or pause for rest (stay in the same node). A walk is described with a string of letters 'L', 'R' and 'P':
The value of the walk is the label of the node we end up on. For example, the value of the walk LR is 5, while the value of the walk RPP is 3.
A set of walks is described by a string of characters 'L', 'R', 'P' and '*'. Each '*' can be any of the three moves; the set of walks contains all walks matching the pattern.
For example, the set L*R contains the walks LLR, LRR and LPR. The set ** contains the walks LL, LR, LP, RL, RR, RP, PL, PR and PP.
Finally, the value of a set of walks is the sum of values of all walks in the set. Calculate the value of the given set of walks.
The first line of the input is an integer Z (1 <= Z <= 15), which means the number of test cases. For each test case, one line containing a string describing the set. Only characters 'L', 'R', 'P' and '*' will appear and there will be at most 10000 of them.
For each test case, output the test case number and the value of the set.