Reese is participating in a prize-guessing game.

There are $N$ ($N > 2$) doors in front of her, with a grand prize behind exactly one of them, and the others are empty. There is a host who knows which door hides the prize. Each time Reese chooses a door (without opening it), the host chooses one door to open from the remaining unopened doors that do not contain the prize, and then gives Reese another chance to choose (Reese can choose to keep her previous choice or switch to any other door she wants). This continues until only two doors remain, at which point Reese's choice becomes her final choice.

Reese wants to win the grand prize, but she has no information. Therefore, she decides to always pick a door that has the "highest probability of having the prize behind it from her perspective." If there are multiple such doors, she chooses one of them uniformly at random. (Obviously, when choosing for the first time, the probability of the prize being behind any door from her perspective is $\frac{1}{N}$, so she will choose one of the $N$ doors at random.)

In other words, Reese's selection process can be abstracted as follows:

while (number of remaining doors >= 2):
    Reese selects a door as described above, without opening it
    if (number of remaining doors == 2):
        This door is Reese's final choice; break;
    The host opens a door as described above (which means the number of remaining doors decreases by 1)
    Reese recalculates the probability of the prize being behind each door

Now, the event organizer has appointed you as the host and asks you to manipulate the game. In other words, each time, you can actively choose which door to open from the remaining doors (excluding the one Reese chose and the one with the grand prize) instead of choosing randomly, with the goal of minimizing the probability that Reese ultimately chooses the prize door. Given $N$, find this minimum probability.

Note: Reese is unaware of your existence. In other words, she still assumes the host is acting normally and does not try to guess your intentions.

Input

Due to some reasons, the input consists of a series of congruence equations, where $N$ is the smallest non-negative integer solution to these equations.

The first line contains a positive integer $T$, representing the number of congruence equations.

The next $T$ lines each contain two integers $a_i, b_i$ ($0 \leq a_i < b_i$), representing $N \equiv a_i \pmod {b_i}$.

Output

If such an $N$ does not exist or $N < 2$, output a single line containing "error" (without quotes). Otherwise, output the answer as a decimal rounded to six decimal places. The evaluation uses full-text comparison.

Examples

Input 1

1
2 1000000007

Output 1

0.500000

Input 2

1
3 1000000007

Output 2

0.666667

Note 2

This is the classic Monty Hall problem.

Initially, Reese has a $1/3$ probability of choosing the correct door. In this case, no matter what you choose, Reese will switch doors and end up with the wrong one.

In the other $2/3$ of cases, you have no choice but to eliminate an incorrect option, leaving her to switch to the correct door.

Subtasks

Subtask 1 (5 points): $T = 1$, $a_i \leq 4$.

Subtask 2 (10 points): $T \leq 10$, if $N$ exists, then $N \leq 6$.

Subtask 3 (10 points): $T \leq 10$, if $N$ exists, then $N \leq 8$.

Subtask 4 (10 points): $T \leq 10$, if $N$ exists, then $N \leq 10$.

Subtask 5 (5 points): If $N$ exists, then $N \leq 200$.

Subtask 6 (25 points): $b_i$ are guaranteed to be pairwise coprime.

Subtask 7 (35 points): No special properties.

For all data, $T \leq 5 \times 10^4$, $\operatorname{lcm}(b_1, b_2, \cdots, b_n) \leq 10^{18}$.

Note

Bayes' theorem: Suppose $B_1, B_2, \cdots, B_n$ are $n$ mutually exclusive events, and $\sum_{i=1}^n P(B_i) = 1$, then

$$P(B_i \mid A) = \frac{P(B_i)P(A \mid B_i)}{\sum_{j=1}^n P(B_j)P(A \mid B_j)}$$

where $P(B_i \mid A)$ denotes the probability of event $B_i$ occurring given that event $A$ has occurred.