Little K was accidentally brainwashed by the LL cult, to the point where he even wants to quit the King Arthur cult. Before he quits, he decides to play one last game of King Arthur. Since it is his final battle, he wants to play it beautifully. As everyone knows, King Arthur is a game that relies on luck, and the activation of skills is probabilistic. As an "African" (someone with bad luck) and a former OIer, Little K naturally hopes to maximize the expected value of the damage dealt. However, he has not written code for many years and cannot even type out a Splay tree correctly, so he hopes you can help him experience what it feels like to be a "European" (someone with good luck).

In this problem, we consider a simplified model of the game.

The player has a set of $n$ cards. During the game, the player arranges the $n$ cards in a certain order, and after the arrangement, the cards are numbered $1$ to $n$ from front to back. In this problem, the order is already fixed, which is the order provided in the input.

Each card has a skill. The probability of the $i$-th card's skill activating is $p_i$, and if it activates successfully, it will deal $d_i$ damage to the enemy. A card can only deal damage to the enemy by activating its skill. Based on real-world factors and Little K's "African" ancestry, $p_i$ will not be $0$ or $1$, i.e., $0 < p_i < 1$.

A game consists of $r$ rounds. In each round, the system starts from the first card and considers each card in order. In one round, for each card considered in sequence:

1. If this card has already activated its skill in this game: 1.1 If this card is not the last one, skip it (consider the next card); Otherwise (it is the last one), end this round of the game.
2. Otherwise (this card has not activated its skill in this game), let this card be the $i$-th card: 2.1 It activates its skill with probability $p_i$. 2.2 If the skill activates, it deals $d_i$ damage to the enemy, and this round ends. 2.3 If this card is already the last one (i.e., $i$ equals $n$), end this round; otherwise, consider the next card.

Please help Little K calculate the expected value of the damage that this set of cards can deal in one game.

Input

The input file is arthur.in. The first line of the input contains an integer $T$, representing the number of test cases. There are $T$ test cases in total. The first line of each test case contains two space-separated integers $n$ and $r$, representing the number of cards and the number of rounds in the game, respectively. The next $n$ lines each contain a real number and an integer, separated by a space, describing a card. The two numbers in the $i$-th line are $p_i$ and $d_i$, representing the probability of the $i$-th card's skill activating (a real number) and the damage dealt by the skill activation (an integer), respectively. It is guaranteed that $p_i$ contains at most 4 decimal places and is a valid probability.

Output

The output file is arthur.out. For each test case, output one line containing a real number, which is the expected value of the damage dealt by this set of cards in one game. For each line of output, your answer will be judged as correct only if the relative error between your output and the standard answer does not exceed $10^{-8}$—that is, $|a-o|/a \le 10^{-8}$ (where $a$ is the standard answer and $o$ is your output). It is recommended to output 10 decimal places.

Examples

Input 1

1
3 2
0.5000 2
0.3000 3
0.9000 1

Output 1

3.2660250000

Input 2

1
10 12
0.3668 857
0.4736 283
0.2321 801
0.6880 555
0.0225 121
0.5814 724
0.0456 60
0.9827 561
0.7015 962
0.1746 960

Output 2

5279.3753475918

Constraints

For all test cases, $1 \le T \le 444$, $1 \le n \le 220$, $0 \le r \le 132$, $0 < p_i < 1$, $0 \le d_i \le 1000$. Unless otherwise specified in the remarks, $p_i$ and $d_i$ in the data are randomly generated. Please be aware of potential real number precision issues and take appropriate measures.