Heights of the Trees

Hasinur_ Criterion 2021 Round 13
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

Submit

Login to submit.

Statistics

72% Solution Ratio
fextivityEarliest, Apr '21
dream.toFastest, 0.2s
Tahmid690Lightest, 8.8 MB
Deshi_TouristShortest, 848B
Toph uses cookies. By continuing you agree to our Cookie Policy.