Programming contests can be very exhausting. After five hours of intensive programming, you want to get some well-deserved rest and make yourself on the way to your hotel. Unfortunately, you don't quite remember the way to get there... but that doesn't matter: In good spirits (due to a successful contest?) you set out.

As you don't know the exact way, you decide to walk around in the following fashion: Start at the contest site (denoted by id 0) and choose a street at random. Follow the street to the next intersection, and choose another street at random. Every street at an intersection has the same probability of being chosen. You might even decide to take the street back where you came from. As you're on foot, you can use the streets in both directions, unlike in "Madrid's One Way Streets".

Your walk stops once you encounter your hotel (id = 300) or one of the tourist information booths (id > 290) where you can ask for the way. You can assume there is at least one path connecting you to either type of object.

Because you don't speak a lot of Spanish (apart from some verbs that you can conjugate thanks to problem "Spanish Conjugation"), you'd like to know the probability that you arrive at your hotel directly, without first arriving at a tourist information booth.

Input

The input consists of several test cases, separated by an empty line.

Each test case starts with S, the number of streets. The following S lines contain two numbers 0 ≤ A, B ≤ 300 each. This means that there is a street connecting intersection A to intersection B. The same street will not appear multiple times in the input.

The input ends with S = 0. This test case should not be processed.

Output

For each test case, print the probability to arrive directly at the hotel, rounded to three decimal places.

Example

Input:
3
0 291
0 292
0 300

2
0 300
291 300

2
0 291
291 300

7
0 292
0 88
0 14
0 300
292 88
88 300
14 300

0

Output:
0.333
1.000
0.000
0.579