Gia đình của bạn vừa mới chuyển đến một thị trấn với một hệ thống giao thông đơn giản: có tất cả ~N~ nút giao thông và ~N - 1~ tuyến đường nối các nút này lại với nhau. Những con đường của thị trấn cho phép bạn di chuyển giữa hai nút giao thông bất kỳ. Mỗi con đường kết nối ~2~ nút khác nhau và có một chỉ số ưa thích nhất định.

Bạn vừa mới chuyển đến nên hiển nhiên chưa thể quen được với hệ thống giao thông nơi đây, vì vậy mỗi khi bạn đang đứng tại ~1~ nút giao thông mà không phải đích đến, bạn sẽ chọn một trong những tuyến đường liên thuộc với nó, kể cả khi điều này khiến bạn đi xa hơn đích đến. Xác suất được chọn của ~1~ tuyến đường bằng với tỉ số giữa chỉ số ưa thích của nó và tổng chỉ số ưa thích của các đường liên thuộc. Ví dụ, nếu có tổng cộng ba đường có thể đi từ ~1~ nút giao thông với chỉ số ưa thích lần lượt là ~1, 2~ và ~3~ thì xác suất được chọn của mỗi đường lần lượt là ~\displaystyle \frac{1}{6}~, ~\displaystyle \frac{2}{6}~ và ~\displaystyle \frac{3}{6}~.

Cho địa điểm nơi xuất phát (ngôi nhà mới của bạn) tại một nút giao thông và đích đến (trường học mới của bạn), hãy tính giá trị kỳ vọng của số lượng tuyến đường mà bạn phải đi.

Input

Dòng đầu tiên chứa một số nguyên ~T~ ~\left(T \le 20\right)~ là số lượng test. Trong ~T~ nhóm dòng sau, mỗi nhóm gồm:

• Dòng đầu chứa ~3~ số nguyên ~N, st, end~ ~\left(1 \le N \le 15;st, end \leq N\right)~ lần lượt là số nút giao thông, vị trí bắt đầu và đích đến.
• Trong ~N - 1~ dòng sau, mỗi dòng chứa 3 số nguyên dương ~u, v, c~ ~\left(u, v \leq N; c \leq 100\right)~ với ý nghĩa: có một tuyến đường nối trực tiếp giữa nút ~u~ và nút ~v~ có chỉ số ưa thích là ~c~.

Output

Với mỗi test, hãy in ra giá trị kỳ vọng của số lượng tuyến đường mà bạn phải đi, làm tròn chính xác đến đúng ~5~ chữ số sau dấu phẩy.

Sample Input

1
3 2 3
1 2 1
2 3 1

Sample Output

3.00000

Note

Có ~50\%~ là bạn sẽ đi thẳng từ ~2~ đến ~3~

Có ~25\%~ là bạn sẽ đi: ~2~ -> ~1~ -> ~2~ -> ~3~

Có ~12.5\%~ là bạn sẽ đi: ~2~ -> ~1~ -> ~2~ -> ~1~ -> ~2~ -> ~3~

...

Kết quả sẽ là: ~1 \times 50\% + 3 \times 25\% + 5 \times 12.5\% + \ldots = 3~