FURYROAD - Fury Road

no tags 

Westland is full of war parties. There is always frequent war occurs in the fury road of Westland. Today is an another great day for the immortal Joe, because he is going to the war with his Kamakrazee war boys in the fury road. So, he sent Slit one of his war boys to count the number of war parties. In the fury road there are multiple war parties fight together, so it is difficult to count the number of war party but, Slit properly know that, if a group of war boys stand together, on the other word if they are adjacent (vertically, horizontally and diagonally) to each other, they would be counted as a single war party. As, there is large number of war parties in the fury road, it is not quite easy to count the number of war parties perfectly. So, Slit needs your help to determine the number of war parties in the fury road.

Now, you are given the number of war boys and their position in the Cartesian plane as (x, y) format which indicates the war boy’s position. Now you have to determine the number of war parties.

Input

The input set starts with single line integer T (1<=T<=50) the number of test cases. Then following T cases starts with an integer N (1<=N<=10000) denoting the number of war boys in the fury road Then next N line contains a pair of integer (Xi, Yi) (0<=Xi, Yi<=1000) denoting the position of i-th war boy.

Output

For each case print “Case X: ” (without the quotes) where X (1≤X≤T) is the case number. And then print the number of War parties in the fury road. Every new case should be printed in a new line.

Example

Input:
3
2
5 5
3 2
6
1 3
0 1
1 2
2 3
4 1
5 0
1
0 0

Output:
Case 1: 2
Case 2: 2
Case 3: 1

hide comments
nimphy: 2018-04-29 13:52:42

@raawr @Mohib 我也来凑热闹! 在一起!在一起!在一起!在一起!在一起!在一起!在一起!在一起!在一起!在一起!在一起!在一起!在一起!在一起!在一起!在一起!在一起!在一起!在一起!在一起!在一起!在一起!在一起!在一起!在一起!在一起!在一起!

jonathanzong: 2017-08-12 11:43:27

@raawr @Mohib 在一起!在一起!在一起!在一起!在一起!在一起!在一起!在一起!在一起!在一起!在一起!在一起!在一起!在一起!在一起!在一起!在一起!在一起!在一起!在一起!在一起!在一起!在一起!在一起!在一起!在一起!在一起!

vengatesh15: 2017-02-19 11:00:28

easy one AC in 1 go:-)

raawr: 2016-01-08 07:26:56

@Mohib You are so adorable :D

Last edit: 2016-01-08 07:27:34

Added by:imranziad
Date:2015-11-25
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY
Resource:AIUB CS Fest 2015 (Ift Khan)