나는 어둠을 공격한다!

드래곤과 던전이 등장하는 유명한 게임처럼, 많은 테이블탑 롤플레잉 게임(RPG)은 게임 속 다양한 무작위 사건을 시뮬레이션하기 위해 주사위를 사용한다. 6면체 주사위만 쓰는 일반적인 보드게임과 달리, RPG에서는 보통 면의 수가 4, 6, 8, 12, 20인 여러 종류의 다면체 주사위를 사용한다. 플레이어는 종종 스킬 체크를 해야 한다. 스킬 체크란 여러 개의 주사위를 굴려 각 눈을 모두 더한 뒤, 그 합을 미리 정해진 목표값과 비교하는 것이다. 주사위 눈의 총합이 목표값 이상이면 스킬 체크는 성공한 것으로 본다.

RPG에서 주사위를 굴릴 때는 주사위 표기법으로 굴릴 주사위의 개수와 종류를 나타낸다. 예를 들어 1d4+2d8은 주사위 세 개, 즉 4면체 하나와 8면체 둘을 굴려 세 결과를 모두 더하라는 뜻이다. 때때로 플레이어는 총합에 보정값(상수 정수)을 더하거나 빼야 한다. 예를 들어 $+3$ 보너스는 1d4+2d8+3으로, $-5$ 페널티는 1d4−5+2d8으로 쓸 수 있다. 각 주사위의 면은 $1$부터 면의 수까지 번호가 매겨져 있어 모든 면이 서로 다른 값을 가진다. 예를 들어 4면체 주사위의 면에는 $1, 2, 3, 4$가 적혀 있다.

스킬 체크에 실패하면 보통 캐릭터에게 나쁜 일이 생기므로, 특정 스킬 체크가 성공할 확률을 아는 것이 중요하다. 목표값과 주사위 굴림 식을 입력받아 그 스킬 체크를 통과할 확률을 출력하는 프로그램을 작성하라.

입력의 첫 줄에는 데이터 집합의 개수를 나타내는 정수 $N$ ($1 \le N \le 100$)이 주어진다. 각 데이터 집합은 T X 형태의 한 줄로 이루어진다. 여기서 $T$ ($0 \le T \le 100$)는 목표값이고, $X$는 주사위 표기법을 담은 문자열이다. $X$에는 공백이 없다.

주사위 표기법 $X$는 하나 이상의 항으로 이루어지며, 각 항은 더하기 + 또는 빼기 − 기호로 구분된다. 각 항은 정수 $M$ ($1 \le M \le 10$)이거나, NdS 형태의 식이다. 여기서 $N$ ($1 \le N \le 6$)은 주사위의 개수이고, $S$는 ${4, 6, 8, 12, 20}$ 중 하나인 면의 수이다. 한 식에서 굴리는 주사위의 총 개수는 $6$을 넘지 않는다.

각 데이터 집합에 대해, 주사위 눈의 합이 목표값 $T$ 이상이 될 확률을 한 줄에 출력한다. 목표값에 절대 도달할 수 없으면 0을 출력한다. 모든 가능한 주사위 굴림에서 항상 목표값에 도달하면(예: 보정값 때문에) 1을 출력한다. 그 외의 경우에는 확률을 기약분수로 출력한다.