Problem D
Gears in Action

Peter works in the Slovak Institute of Gears. After years of hard work he has constructed a special machine whose only purpose is to rotate a lot of gears. After 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, where for every $i$ the $i$-th gear is connected to the gears $i-1$ and $i+1$ – except for gears $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 gears rotate at the same speed. 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. In the beginning the gears are rotated so that the 0-th tooth of each gear is next to its red mark.

Peter has imagined a configuration of gears. 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

The first line of the input contains one integer $M, M\leq 100$ – the number of test cases. For each test case there is one integer $N (1\leq N\leq 500)$ denoting the number of gears. $N$ lines follow, one for each gear. The $i$-th line contains numbers $a_ i$ and $b_ i$ as described above and $0\leq b_ i < a_ i \leq 10^9$. You may assume that the least common multiple of all $a_ i$ is at most $10^9$ in cases where $N>2$ and at most $10^{18}$ when $N=2$.

Output

For each test case output one line with the first time when, for all $i$, the $i$-th gear will have the tooth number $b_ i$ next to the red mark. If this never happens, output one line with the string "Impossible" (without the quotes) instead.

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

22
Impossible