There are rockets launched to a plain, which can be regarded as a two-dimensional plane.The rockets land in sequence.The rocket will bring up smoke when it lands. The range is a circle with radius .if the smoke cover the rocket, it will cause the loss of .How much loss does each rocket cause.

输入描述:

The first line contains an integer representing the number of test cases.
For each test case, the first line contains an integer  representing the number of the rockets.
the next  line followed. the  line contains the coordinates of the  rocket , the loss when it is covered , and the range of smoke .
It is guaranteed that there are no more than 1 testcases with 
The rocket may land at the same coordinates
all test cases create by randomly

输出描述:

For each test case, print  line representing the loss caused by  rocket.

1
5
1 1 1 3
2 2 2 1
3 3 4 2
4 4 8 2
5 5 16 4

1
2
6
12
28