Nerd Poker is a podcast where you get to listen in on a group of people playing a game of Dungeons and Dragons. There is a lot of dice rolling in this game, using a lot of different types of dice. There are dice with ~4~, ~6~, ~8~, ~10~, ~12~, and ~20~ sides that are regularly used to play the game. In combat and at other critical junctures of the game, low rolls are often bad.

The Nerd Poker players are superstitious, so before entering combat they take their dice and "roll out the ones". They start with their ~20~ sided dice, then do their ~12~ sided, ~10~ sided, etc. They roll all the dice of the same type at once, set aside any that show a ~1~, then roll the remaining dice, set aside the ~1~'s again, and continue this process until they have rolled a ~1~ on every die.

For example, Brian has ~3~ four-sided dice. On the first roll, they show: ~1~, ~3~, and ~3~, so he sets aside the ~1~ and rolls the other two again. This time he gets a ~1~ and ~4~, so he sets aside the ~1~ and continues to roll the last die. It takes him ~3~ more rolls before he gets a ~1~, for a total of ~5~ rolls. But how many rolls should Brian expect to have to make? Or to put it another way, if Brian rolled out the ones on his ~3~ four-sided dice an arbitrarily large number of times, what would be the average number of rolls required?

The input will contain ~10~ test cases. Each test case consists of a single line with ~2~ positive integers ~N~ and ~S~ where ~N~ is the number of dice and ~S~ is the number of sides on each die ~(1 \le N \times S \le 500)~. Your job is to output a line containing a single integer for each test case, representing the expected number of rolls required to roll out all the ~1~'s. Your answers should always be rounded up.

Note that the sample input below contains only ~3~ test cases but the actual data files will contain ~10~.

Sample Input

1 20
125 4
25 20

Sample Output

20
20
75

Question Development Team

Sam Scott (Sheridan College)
Kevin Forest (Sheridan College)
Stella Lau (University of Cambridge)
Reyno Tilikaynen (University of Waterloo)
David Stermole (ECOO-CS President)
John Ketelaars (ECOO-CS Communications)

Educational Computing Organization of Ontario - statements, test data and other materials can be found at ecoocs.org