E |
Extreme Primitive Society |
Do
not be misled by the name. Primitive society is a community of very advanced
intelligent unisexual beings, called the primitives. The reason that they are
called primitives is that they are all primitive geometric shapes, rectangles.
Every member of the primitive society have two genetic traits, width(w)
and height(h), both can be expressed as positive integers. The primitive
society have in fact so advanced in science and technology that, now they
reproduce only through the means of genetic engineering. Their reproduction
system works as follow.
Two
primitives deposit their gene samples in a Generation Creating Machine (GCM).
The GCM then performs genetic engineering tasks to produce up to 4
offspring. Say the parent primitives had genetic traits (w1,h1) and (w2,h2)
respectively. Then the 4 offspring would have genetic traits (w1,h1)
, (w2,h2) , (w1,h2) and (w2,h1) respectively.
After this, a mutation is performed but this is
optional and GCM decided this randomly. The mutation process is defined as the
incrementing or decrementing of h value by 1 and / or
incrementing or decrementing of w value by 1. And thus, a new
generation of primitives is born. See fig. for better understanding of the
procedure.
Due
to their scientific advancements, the primitives have become immune to
everything except the weather change. Therefore, they do not need to reproduce
very often to ensure survival of their species. Once in ten years or so they
deposit their gene samples to the GCM. Say there are n people in the
current generation, then the GCM uses the genes from every individual of the
current generation with every other individual performing n(n-1)/2
mating. The GCM can also apply mutation on some of the resulting offspring to
increase their fitness. A primitive is considered absolutely fit if both of its
genetic traits have same value, i.e. the rectangle is a square.
Note
that, although n(n-1)/2 mating are performed, at most 2n(n-1)
offspring are born in the next generation. Why up to 2n(n-1), not
exactly 2n(n-1) ? Because they don’t have any need for people with
redundant genetic configurations and the GCM makes sure that only one person of
each possible genetic configuration will remain in the society.
Given
an initial population of primitives, your job is to calculate the minimum
number of generations should pass before an absolutely fit individual is born
in this society.
Input
There
will be multiple test Cases, not more than 1010. Each case starts with
an integer n(>=2) on a line by itself. This is the number of
individuals in the initial population. Following will be n lines, each having 2
positive integers representing the genetic configuration of each individual of
the society. All numbers will be positive integers not exceeding 100.
Output
For
each test case of input, print one line of output beginning with “Case x : “
where x is the test case number. This text should be followed by the minimum
number of generations required before an absolutely fit individual is born in
this society.
Sample Input |
Sample Output |
3 35
40 30
35 32
44 3 35
68 70
1 79
25 |
Case
1 : 1 Case
2 : 1 |
Problem setter: Raiyan Kamal Special Thanks: Sabbir
Yousuf