Fjölkveradalur P15243

In a remote place in central Iceland there is a forgotten, small, dark hidden valley called Fjölkveradalur (“the valley with many geysers”). As the name indicates, the place contains a lot of eruptive hot springs. But there is something weird about this valley. On the one hand, the geysers’ regularity cannot be natural: for each geyser, the time between two of its consecutive eruptions is fixed; moreover, this time, when expressed in seconds, is always an exact integer number. On the other hand, some archaic, many-thousand-year-old runes have been found on strange rocks around the geysers. And according to dating analyses, these runes were written much before any known human presence in the island.

These intriguing facts have induced the study and decription of the runes’ meaning. The astounding conclusion is that, if one day all the geysers erupt at the same instant, the nearby volcano Hekla (traditionally known as “the gateway to Hell”) will open its doors and the world will be anihilated. Since this could be a little bit disturbing, you are asked to write a program to foresee that moment.

Input

Input consists of several test cases, one per line. Each line has the description of one or more geysers, each with a pair of natural numbers p (the length in seconds of the period) and n (the number of seconds until the next eruption). So, for instance, 3 0 describes a geyser that erupts every three seconds and that is erupting just now. Assume 0 ≤ n < p ≤ 20.

Output

For every test case, print the number of seconds until the destruction of the world. If that moment will never arrive or if it is just now, state so as shown in the examples.