Description

Recently, archaeologists in China discovered several secret chambers in a new pit of the Terracotta Army, each accessible through a peculiar door. How can a chamber be entered?

On the door to the $i$-th chamber, there are $a_i$ dials. The $j$-th dial of this chamber is evenly divided into $b_{i,j}$ cells, numbered in clockwise order as $0, 1, \dots, b_{i,j}-1$. Each dial has a hand (similar to a clock). Approximately every 1.53 seconds, a hand that was pointing at the cell numbered $x$ advances to point at the cell numbered $(x+1)\mod b_{i,j}$. When, for a door, the hands on all its dials simultaneously point to the cell numbered $0$, the door opens.

However, when the chambers were discovered, the hands on the dials pointed to various indices. Based on the opening rule, it was determined that some chambers can never be opened. Your task is to determine which doors can possibly be opened.

Input Format

The first line contains $n$, the number of chambers. The data that follows is divided into $n$ groups, each describing one door. In group $i$, the first line contains $a_i$, the number of dials on that door. Each of the next $a_i$ lines contains two integers: the first is $b_{i,j}$, and the second is the index of the cell the hand was pointing to when the chamber was discovered.

Output Format

Output $n$ lines. For the $i$-th chamber, print possible if its door can be opened; otherwise, print impossible. Note: use lowercase.

2
2
5 3
4 2
2
4 3
6 2

possible
impossible

Hint

Constraints: For $100\%$ of the testdata, $n<100$.

Translated by ChatGPT 5