Heights of the Trees

There are many long trees in a forest. You will be given some relevant information about the trees and your task is to guess the heights of the trees. Let me describe the relevant information.You will be given a list of $N$ pairs. Each pair consists of an integer number $D$ and $F$. Here,

• $D$ $=$ A positive integer number.

• $F =$ Number of trees which have a height of $H$ where $H \equiv 0 \mod D$

Note that there will be no two pairs in the list such that they contain the same value of $D$. It is guaranteed that the list contains all the divisors of the heights. You have to guess the heights of the trees. It is guaranteed that an unique solution exists for the given list of pairs.

Input

The first line of the input contains a single positive integer number $T(1\leq T \leq 10^5)$ where T denotes the number of testcases.

Each test case starts with a single integer $N(1\leq N \leq 10^5)$. Each of the next N lines will contain two positive integer numbers $D(1 \leq D \leq 10^5)$ and $F(1\leq F \leq 10^{5})$.

Note that, the sum of all $N$ in the input file will be at most $10^6$

Output

For each test case print “Case T:” in a line, where T denotes the test case number. Let there be $M$ unique heights of trees for this test case. Print $M$ in the next line. After that, You have to print $M$pairs in the next $M$ lines. The pair will contain two space separated integers $H_{i}$ and $X_i$. Here,

• $H_{i} = i^{th}$shortest unique height of the trees.

• $X_{i} =$Number of trees of height $H_{i}$

Sample

Input	Output
1 3 1 3 2 2 4 1	Case 1: 3 1 1 2 1 4 1