One day, you have a female friend.

You plan to spend $k$ days with her. There are many entertainment options available each day, and you need to choose one to perform (only one project can be performed per day). For example, going to the movies together, going to a theme park, or going shopping, etc. There are a total of $n$ types of projects. Naturally, you will feel bored if you repeat any project too many times, so the $i$-th project can be performed at most $c[i]$ times.

Although you have a high IQ, your EQ is concerning. Even though you prepare these activities with the hope of making her happy, your clumsy expression and overly rational actions might lead to unexpected outcomes. After careful calculation, you find that if you perform the $i$-th project on a certain day, she should be happy if everything goes smoothly, but there is a probability of $a[i]$ that she will be unhappy. If she was originally happy, but you suddenly make her unhappy today, she will feel disappointed, and her favorability towards you will drop significantly. You hope to avoid this situation as much as possible, so you need to arrange the projects for each of these $k$ days to minimize the expected number of times she feels disappointed.

Your female friend cares about you very much, so her mood only changes because of you. Before the first day, because you have not invited her to any activities, she is unhappy.

Input

The first line contains a non-negative integer $t$, representing the total number of test cases.

For each test case, the first line contains two non-negative integers $n$ and $k$, representing the number of projects you have prepared and the number of days you spend with her, respectively ($n \le 10^5, k \le 10^9$).

The next $n$ lines each describe a project in the format "x[i]/y[i] c[i]", where all three numbers are non-negative integers. This indicates that after completing this project, she has a probability of $x[i]/y[i]$ of being unhappy, and this project can be performed at most $c[i]$ times ($x[i], y[i] \le 10^4, c[i] \le 10^9$).

Output

For each test case, output the minimum expected number of times she feels disappointed, rounded to 6 decimal places.

Examples

Input 1

3
1 2
0/1 3
1 2
1/1 3
1 2
1/2 3

Output 1

0.000000
0.000000
0.250000

Note

Consider the third test case. Since there is only one project, you have to arrange it every day. Before the first day, she is always unhappy. There are four scenarios: First day unhappy, second day unhappy. First day happy, second day unhappy. First day unhappy, second day happy. First day unhappy, second day unhappy.

Since the probability of the project making her happy or unhappy is $0.5$ each day, these four scenarios occur with equal probability. She feels disappointed only in the second scenario. Therefore, the answer is $(1 \times 1 + 0 \times 3) / 4 = 0.25$.

Constraints

• For the first 10% of data, $n, k \le 5$.
• For the first 30% of data, $n, k \le 7$.
• For the first 40% of data, $n, k \le 10$.
• For the first 60% of data, $n \le 1000, k \le 10^5$.
• For 100% of the data, $n \le 10^5, k \le 10^9$. The number of test cases is not too large, approximately no more than 10. The data guarantees that the fractions are meaningful and $\sum c[i] \ge k$.