Dab is a petty thief with a sweet tooth. One fine day Dab was caught stealing traditional Indian sweets from Pattanaik sweet corner. Being a lazy lad, Dab was immediately caught and forced to reveal what sweet he had. Now there are n boxes numbered 1 to n each containing three type of sweets i.e Gulab Jamun, Rasgulla and ladoo.

Given that Dab had stuffed his mouth with a sweet "X" find the probability that he stole from the kth box. 

Input

First line contains T the number of test cases.

Each test case contains the value of n(the number of boxes). The following n lines contains three integers each. Each of which denote the number of ladoos, Gulab Jamun and Rasgulla in each box respectively.

The (n+1) th line of each test case contains the value of k followed by character 'L' or 'G' or 'R' where 'L' denotes a ladoo, 'G' denotes a gulab jamun, 'R' denotes a Rasgulla.

Output

For each test case output the probability that dab stole from the kth box. Print the value rounded off to 9 decimal places.

Example

Input:
1
3
5 5 5
3 4 5
2 4 5
2 L

Output:
0.326732673

Constraints:

1<=t<=20

1<=n<200

1<=k<=n

1<= number of each type of sweet <200