Problem E
Mushroom Misery
Input: Standard Input

Output: Standard Output

Time Limit: 2 Seconds

The Institute of Ubiquitousness in Lichtenstein, LIU, conducts a project where the effect of a special type of fungi, sphera carnelevarium, is studied. This fungus is very special, since it grows in a circular fashion from its centre, without interference from other objects or other individuals.

Until now, the impact of this forest-living creature has been measured by examining a grid consisting of n*n squares of size 1 m². A grid is considered affected, if fungi are present in the square, otherwise it is considered clean. Grids, where the fungus merely touches the border of the square are not considered affected.

Of course, the task of examining grids is tedious and now unnecessary, since Prof. Muggel discovered that the grow rate is exactly 2.718281828 m/day. Now, counting the number of affected squares should be like a stroll in the park, right? Since there are a lot of old data, which will be compared to the new data, the rules of counting the squares must be the same. Do not use data types with unnecessary low precision in your calculations.

 

Fig: This figure corresponds to the sample input

Input

On the first line of input there is one integer, N <= 10, giving the number of test cases in the input. After this line, N test cases follows. Each test case starts with a line containing two integers size, n

such that 0 < size <= 1000000, 0 < n <= 1000, where size is the size of the grid in meters and n is the number of individuals in the test grid. After this line, n lines follows, each line consisting of three decimal number, 0 <= x <= size, 0 <= y <= size, 0 < r<= size, where x and y are the zero-based coordinates of the center of the individual and r is the (estimated) radius in meters.

Output

For every test case, output one line containing the number of affected squares (a number between 0 and size²). However, the number of affected squares is always less than 1000000000 (10⁹).

Sample Input                               Output for Sample Input

3 3 0.94

 Problem setter: Andreas Björklund, Source: Swedish National Contest