Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Heights of the Trees

By Hasinur_ · Limits 1s, 512 MB

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 NN pairs. Each pair consists of an integer number DD and FF. Here,

  • DD == A positive integer number.

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

Note that there will be no two pairs in the list such that they contain the same value of DD. 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(1T105)T(1\leq T \leq 10^5) where T denotes the number of testcases.

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

Note that, the sum of all NN in the input file will be at most 10610^6

Output

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

  • Hi=ithH_{i} = i^{th}shortest unique height of the trees.

  • Xi=X_{i} = Number of trees of height HiH_{i}

Sample

InputOutput
1
3
1 3
2 2
4 1
Case 1:
3
1 1
2 1
4 1

    Discussion

    Statistics


    72% Solution Ratio

    fextivityEarliest, 2w ago

    YouKnowWhoFastest, 0.2s

    Tahmid690Lightest, 8.8 MB

    YouKnowWhoShortest, 885B

    Submit

    Login to submit

    Editorial

    The list of heights is a subset of the DDD values in the given lists. The solution is given below: ...

    Related Contests