Each period, a strategy has m possible outcomes. Outcome s occurs with probability w_s / (w_1 + ... + w_m) and has simple return r_s = a_s / 100: if you stake a fraction f of your capital, your capital is multiplied by 1 + f * r_s.

The expected logarithmic growth of your capital under stake f is

G(f) = sum over s of p_s * ln(1 + f * r_s).

For each of T given strategies, choose a stake f in [0, 1].

Input

The first line contains the integer T. Each of the next T lines describes one strategy: the integer m, followed by m pairs w_s a_s.

Output

T lines, your chosen stake f for each strategy in order.

Scoring

Each strategy is scored as G(f) / G_max, clamped to [0, 1], where G_max is the maximum of G over [0, 1] — the fraction of the achievable growth rate that your stake captures. A stake with G(f) <= 0 scores 0; in particular, a stake for which some outcome with positive probability multiplies your capital by 0 has G(f) = -infinity and scores 0. If G_max = 0 (the strategy has no profitable stake), you score 1 for f = 0 and 0 for any f > 0. The score of a test file is the average over its T strategies, and the total score is the average over test files, times 100.

Constraints

1 <= T <= 200

2 <= m <= 10

1 <= w_s <= 10^6

-100 <= a_s <= 500, and at least one a_s is nonzero

Note

In the first sample, the first strategy wins 100% with probability 0.6 and loses everything with probability 0.4. Submitting f = 0.1 for it gives G(0.1) = 0.6 * ln(1.1) + 0.4 * ln(0.9) = 0.0150419..., while G_max = 0.0201355..., so it scores G(0.1) / G_max = 0.747033.... Submitting f = 1 for it scores 0: with probability 0.4 the capital is multiplied by 0.