1740. Gulliver

From Jonathan Swift's book we know that Gulliver visited Lilliputia. Recently historians found out that he actually visited `N` countries, where small people live, surrounded by things, animals and plants of the same small size. In each of those countries little people were afraid of Gulliver in the beginning, but after some time passed they understood that such a neighborhood brings them a lot of benefits, and they tried to help him. For example, Lilliputians were making bed for Gulliver from their small mattresses sewn together. Lilliputians knew how many times they are smaller than Gulliver. Pretty fast they found out how many mattresses they need to sew for him. But they had problems making the bed, because of their small height they sometimes couldn’t make the mattress thick enough.

The first string of input file consists of single integer `N` (`N\ <\ 25`) — number of courtiers, which Gulliver has visited. Subsequent `N` strings are consisting of two integer numbers, divided by space: `K` (`2\ ≤\ K\ ≤\ 100`), representing how many times Gulliver is bigger than Lilliputians, `M` (`2\ ≤\ M\ ≤\ 100`), representing the number of layers in the mattress.

Output data file consists of `N` strings with one integer number in each, representing the number of Lilliputian mattresses used to make one for Gulliver.

2 
2 2
12 4

8
576