Zadanie

Juchú Vianoce

Počet bodov: 60, časový limit: 100ms

Blížia sa vianoce a preto treba ozdobiť stromček. Vianočný stromček je Trie - vyhľadávací strom v ktorom hrany reprezentujú znaky a teda každý vrchol reprezentuje prefix reťazca daného cestou k nemu, pričom každý vrchol reprezentuje unikátny prefix (cs.wikipedia.org/wiki/Trie).

Ozdobovanie stromčeka je v tvojej rodine dlhoročnou tradíciou do ktorej sa všetci zapájajú. Ozdobovací rituál prebieha nasledovne: každý člen rodiny si do ruky zoberie svetelnú reťaz a všetci naraz ich šmaria na stromček. Samozrejme, svetelná reťaz je perfektne náhodný binárny reťazec dĺžky \(L\) (reťazce sa medzi hodmi môžu opakovať) a keď pristane na strome, znamená to, že sme ju vložili do Trie.

Aký je očakávaný počet vrcholov vianočného stromčeka, ak má tvoja rodina \(N\) členov?

Vstup a výstup

Na prvom riadku je jedno celé číslo \(T\) - počet otázok.

Nasleduje \(T\) riadkov. Na \(i\)-tom riadku sú dve celé čísla \(n_i\) a \(l_i\), udávajúce \(i\)-tu otázku tvaru “Aký je očakávaný počet vrcholov Trie ak do nej vložím \(n_i\) náhodných binárnych reťazcov dĺžky \(l_i\)?”.

Na výstup vypíšte \(T\) riadkov, pričom na \(i\)-tom riadku bude jedno číslo - odpoveď na \(i\)-tu otázku. Odpovede vypisujte zaokrúhlené na \(2\) desatinné miesta, vždy vypíšte práve \(2\) (slovom dve) desatinné miesta.

Obmedzenia

Vo všetkých testovacích sadách bude platiť \(0 \leq T \leq 50\), \(1 \leq N, L \leq 300\) a \(1 \leq n_i \leq N\) a \(1 \leq l_i \leq L\) pre všetky \(i\). Navyše v jednotlivých testovacích sadách bude obmedzenie na N a L postupne 5, 10, 20, 100 a 300 - za každú sadu dostanete 20% bodov.

Príklady

Input:

2
1 3
2 2

Output:

4.00
4.25

V prvej otázke existuje 8 možných reťazí, po vložení ľubovoľnej z nich bude mať strom 4 vrcholy.