## IPSC 2005

## Problem G – Gears In Action

Peter works in the Slovak Institute of Gears. After years of hard work he has
constructed a special machine. Its only purpose is to rotate a lot of gears.
After he was watching it for three hours (it makes a good mechanical "screensaver"),
he got interested in one mathematical problem.

In the machine there are **N** gears next to each other. (This means that for each
**i** the wheel **i** is connected to the wheels **i-1** and **i+1** –
except for wheels **1** and **N** that have only one neighbor each.)
The hidden engine rotates the
first gear clockwise one tooth per second. As the gears are connected, all other wheels
rotate at the same speed, too. The **i**-th gear has **a**_{i} teeth
numbered counter-clockwise from 0 to **a**_{i} − 1.
There is also one red mark next to each gear. At the beginning the wheels are rotated
so that the 0th tooth of each wheel is next to its mark.

Peter has imagined a configuration of wheels. In his configuration for all
**i** the **i**-th wheel has the tooth **b**_{i} next to its red mark.
He would like to know whether his machine will reach this configuration –
and if yes, when it will happen for the first time.

### Input specification

The first line of the input contains one integer **M** – the number of test
cases. For each test case there is one integer **N** denoting the number of gears.
**N** lines follow, one for each gear. On the **i**-th of these lines there are
the numbers **a**_{i} and **b**_{i} described above.

### Output specification

For each test case output one line with the first time when the **i**-th
gear will have the tooth number **b**_{i} next to the red mark
(for all **i** at the same time). If this never happens, output one line
with the string "`Impossible`

" (without the quotes) instead.

### Example

**Input:**

2
3
5 2
4 2
6 4
2
4 3
6 0

**Output:**
22
Impossible

**Credits:**

**Problemsetter(s):** Lukas

**Contest-related materials:** Lukas, Mirko