I'm Attacking the Darkness!

Many tabletop role-playing games (RPGs), including a rather famous one involving dragons and dungeons, use dice to simulate the random events in the game. Unlike most board games that use six-sided dice, RPGs typically use several polyhedral dice with 4, 6, 8, 12, or 20 sides. A player is often required to make a skill check: roll a set of dice, add the individual rolls together, and compare the sum against a pre-determined target value. If the total is equal to or greater than the target value, the skill check succeeds.

A dice roll is written using dice notation, which indicates how many and what kind of dice to roll. For example, 1d4+2d8 tells the player to roll three dice — one 4-sided die plus two 8-sided dice — and add the three results together. A player may also add or subtract a modifier (a constant integer) to the total. For instance, a $+3$ bonus may be written as 1d4+2d8+3, while a $-5$ penalty may be written as 1d4−5+2d8. The faces of each die are numbered from $1$ up to the number of sides, so every face is unique; for example, a 4-sided die has faces numbered $1, 2, 3, 4$.

Because failing a skill check is usually bad for the character, it is important to know the chance that a skill check succeeds. Write a program that reads a target value and a dice-roll expression, then prints the probability of passing the skill check.

The input begins with a line containing a single integer $N$ ($1 \le N \le 100$), the number of data sets. Each data set is a single line of the form T X, where $T$ ($0 \le T \le 100$) is the target value and $X$ is a string containing the dice notation. $X$ contains no spaces.

The dice notation $X$ contains one or more terms separated by a plus + or minus − sign. Each term is either an integer $M$ ($1 \le M \le 10$) or an expression of the form NdS, where $N$ ($1 \le N \le 6$) is the number of dice and $S \in \{4, 6, 8, 12, 20\}$ is the number of sides. The total number of dice rolled in any one expression does not exceed $6$.

For each data set, print a single line containing the probability that the dice roll is greater than or equal to the target value $T$. If the target value can never be achieved, print 0. If the target value is always achieved by every possible dice roll (for example, because of modifiers), print 1. Otherwise, print the probability as a fraction reduced to lowest terms.