403380: GYM101147 F Bishops Alliance

Chessforces is coming into a great war. The Knights Alliance is aiming to attack the Bishops Alliance land, it is up to you to help bishops defending their homeland.

In order to defeat the attacking knights, bishops want to make their defense line as big as possible. Defense line is a set of bishops on the chessboard where each pair of bishops in this set satisfies OK relation. OK relation between bishop i and bishop j is satisfied if they are on the same diagonal and the number of squares on the diagonal path between i and j is at least equal to p_i² + p_j² + C, where p_k is privacy distance for bishop k and it is given for each bishop on the board, C is a given constant. Note that the path between two bishops includes both bishops squares.

Given the coordinates of each bishop on the chessboard, help them to find the defense line with maximum number of bishops.

First line contains number of test cases T. Each test case contains one line with (0 < n ≤ 10⁵) size of the chessboard edge, (0 < m ≤ 10⁵) number of bishops and the constant (0 ≤ C ≤ 10⁵) then m line follows, the i^th line of them contains three integers: (1 ≤ r_i, c_i, p_i ≤ n) where (r_i,c_i) is row number and column number of the i^th bishop and p_i is the privacy of the i^th bishop.

Print a single integer, the size of the defense line with maximum number of bishops.

1
8 5 2
7 7 1
4 4 1
3 5 1
2 6 2
4 8 1

2

Large I/O files. Please consider using fast input/output methods.

First test case explanation, columns go from left to right and rows go up to bottom, bishops labeled with borders are included in the defense line.