Deadly Disease

Time Limit : 2 Second

Memory Limit : 64 MB

Submission: 43

Solved: 15

Queen of honey was deeply shocked when she heard the news that some rooms in her honeycomb is infected with serious virus. To make things worse, each infected room will infect all the rooms which share an edge with it in a second. Because she is so sweet that you think you should help her. however, due to the fact that you do not know much about virus, you decide to be ready to tell her, how many rooms in her honeycomb will be infected in K(0<=K<=10^7) seconds.

First comes an integer T (T<=50), indicating the number of test cases. For each test case, there is two integers N and K. N indicates how many rooms are initially infected, then comes the coordinates of the initially infected rooms, they are represent as (i,j) (0<=i,j<=30). One room can only be infected once and no two coordinates will be the same. Queen's honeycomb should be considered infinitely large.

Coordinates are calculated in this way:

A single integer represent the total number of infected rooms after K seconds.

sample input
1 2 0 0
2 1 0 0 1 2
sample output

Problem Setter : Han Yin
© 2015 HUST ACMICPC TEAM. All Right Reserved.