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 pi2 + pj2 + C, where pk 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 ≤ 105) size of the chessboard edge, (0 < m ≤ 105) number of bishops and the constant (0 ≤ C ≤ 105) then m line follows, the ith line of them contains three integers: (1 ≤ ri, ci, pi ≤ n) where (ri,ci) is row number and column number of the ith bishop and pi is the privacy of the ith bishop.
Print a single integer, the size of the defense line with maximum number of bishops.
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.
## Input
First line contains number of test cases T. Each test case contains one line with (0 < n ≤ 105) size of the chessboard edge, (0 < m ≤ 105) number of bishops and the constant (0 ≤ C ≤ 105) then m line follows, the ith line of them contains three integers: (1 ≤ ri, ci, pi ≤ n) where (ri,ci) is row number and column number of the ith bishop and pi is the privacy of the ith bishop.
## Output
Print a single integer, the size of the defense line with maximum number of bishops.
[samples]
## Note
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.
**Definitions**
Let $ T \in \mathbb{Z} $ be the number of test cases.
For each test case:
- Let $ n, m, C \in \mathbb{Z} $, where $ n $ is the chessboard edge size, $ m $ is the number of bishops, and $ C \geq 0 $ is a constant.
- Let $ B = \{ (r_i, c_i, p_i) \mid i \in \{1, \dots, m\} \} $ be the set of bishops, where $ r_i, c_i \in \{1, \dots, n\} $ are row and column coordinates, and $ p_i \in \{1, \dots, n\} $ is the privacy distance of bishop $ i $.
**OK Relation**
Two bishops $ i $ and $ j $ satisfy the OK relation if:
1. They lie on the same diagonal (i.e., same $ r_i - c_i $ or same $ r_i + c_i $), and
2. The number of squares on the diagonal path between them (including both endpoints) is at least $ p_i + p_j + C $.
**Constraints**
1. $ 1 \leq T \leq \text{large} $
2. $ 0 < n \leq 10^5 $, $ 0 < m \leq 10^5 $, $ 0 \leq C \leq 10^5 $
3. $ 1 \leq r_i, c_i, p_i \leq n $ for all $ i \in \{1, \dots, m\} $
**Objective**
Find the maximum size of a subset $ S \subseteq B $ such that every pair of bishops in $ S $ satisfies the OK relation.