There are $n$ point charges at pairwise distinct positions on a number line, numbered $1,2,\ldots,n$. The $i$-th point charge has charge $q_i$ and coordinate $x_i$. In this problem, the magnitude of the Coulomb force between two distinct point charges $i$ and $j$ is defined as $\frac{q_iq_j}{(x_i-x_j)^2}$.

You need to partition all the charges into two nonempty sets $A$ and $B$. Some charges may already have been assigned to one of the sets, and these assignments cannot be changed.

Complete the remaining assignments so that the minimum force over all pairs of distinct charges belonging to the same set is as large as possible.

Input

The first line contains an integer $T$ ($1\le T\le 1000$), the number of test cases.

The first line of each test case contains an integer $n$ ($4\le n\le 10^5$), the number of point charges.

Each of the next $n$ lines contains two integers $q_i,x_i$ and a character $s_i$ ($1\le q_i\le 15000$, $1\le x_i\le 2\times 10^5$; $s_i$ is A, B, or ?), describing the charge, coordinate, and assignment of the $i$-th point charge:

• If $s_i$ is A, the charge has already been assigned to set $A$.
• If $s_i$ is B, the charge has already been assigned to set $B$.
• If $s_i$ is ?, the charge has not yet been assigned to either set.

Within each test case, all coordinates are pairwise distinct, and at least one charge is unassigned.

The sum of $n$ over all test cases does not exceed $5\times 10^5$.

Output

For each test case, output one line containing the maximum possible value of the minimum force between two distinct charges in the same set. Express the answer as a fraction in lowest terms, in the format p/q, where $p$ and $q$ are positive coprime integers.

Examples

Input 1

2
5
3 6 ?
2 4 ?
3 1 ?
5 7 ?
4 2 ?
4
1 1 A
2 2 B
3 3 ?
4 4 B

Output 1

10/9
2/1