POLSKI SPOJ

Józio i Rózia nie mogą zaznać spokoju. Dzieci spędzają wakacje pod opieką swojego przyszywanego wuja Piotra. Postanowił on na ten czas wzbogacić ich dietę w bardziej pożywne produkty niż kanapki z paprykarzem i parówki z mięsa oddzielanego mechanicznie. Na śniadania zaproponował płatki owsiane. Widząc u dzieci brak entuzjazmu, nawet zalążki buntu, pozwolił dzieciom wybrać ich rodzaj. W sklepie Piotr nalegał na płatki bogate w makro- i mikroelementy, jednak dzieci szybko chwyciły w ręce inne, podłej jakości, ale z dołączonymi naklejkami. Po krótkiej lekturze zasad tej 'promocji' ich opiekun stwierdził, że nawet jedząc je trzy razy dziennie przez cały rok, nie zbiorą nawet połowy kolekcji. Dzieci wróciły do domu nadąsane, podejrzewając wujaszka o tanie oszustwo (Józio: Nie można tego wyliczyć! Rózia: I to tak szybko!). Czy słusznie?

Zakładamy, że wszystkie naklejki są jednakowo rzadkie i prawdopodobieństwo ich zdobycia nie zmienia się. Naklejki w paczce mogą się powtarzać!

Wejście

W pierwszej linii liczba całkowita t oznaczająca liczbę przypadków testowych. W kolejnych t liniach pary liczb całkowitych n i k oznaczających kolejno rozmiar pełnej kolekcji oraz ilość naklejek dołączona do jednego pudełka płatków.

Wyjście

Dla każdego przypadku jedna liczba całkowita określająca ile przynajmniej pudełek trzeba zakupić aby przeciętnie zgromadzić całą kolekcję.

Ograniczenia

1 <= n,k < 10^9
1 <= t <= 10^5

Przykład

Wejście:
1
10 4

Wyście:
8