SP1453 OPTSUB - Optimal Connected Subset

- A point _P_(_x_,_y_) is called an integer point if and only if both _x_ and _y_ are integers. - _W_ is the set which contains all the integer points on the plane. - Two integer point _P_(_x_,_y_) and _Q_(_x'_,_y'_) are called adjacent if and only if _|x-x'|+|y-y'|=1_. - _S_ is a set of integer points if and only if _S_ is a limited subset of _W_. - If _S_ is a set of integer points, _R_ and _T_ belong to _S_,and there exist a limited integer point sequence _Q_ $ _{0} $ (=_R_),_Q_ $ _{1} $ ,_Q_ $ _{2} $ ,...,_Q_ $ _{k} $ ,_Q_ $ _{k+1} $ (=_T_) which satisfies that - _Q_ $ _{i} $ !=_Q_ $ _{j} $ iff _i_!=_j_ - _Q_ $ _{i} $ and _Q_ $ _{i+1} $ are adjacent, for each 0

The very first line of the input contains a single integer _T_, the number of test cases. _T_ blocks follow. For each test case, the first line contains a single integer _N_=|_V_|(_N_

_T_ lines,each contains a single integer - the maximum sum of weights.