B'Polycarp is very fond of playing the game Minesweeper. Recently he found a similar game and there are such rules. There are mines on the field, for each the coordinates of its location are known ( x_i, y_i ). Each mine has a lifetime in seconds, after which it will explode. After the explosion, the mine also detonates all mines vertically and horizontally at a distance of k (two perpendicular lines). As a result, we get an explosion on the field in the form of a "plus" symbol ( '+ '). Thus, one explosion can cause new explosions, and so on. Also, Polycarp can detonate anyone mine every second, starting from zero seconds. After that, a chain reaction of explosions also takes place. Mines explode instantly and also instantly detonate other mines according to the rules described above. Polycarp wants to set a new record and asks you to help him calculate in what minimum number of seconds all mines can be detonated. The first line of the input contains an integer t ( 1 <= t <= 10^4 ) -- the number of test cases in the test. An empty line is written in front of each test suite. Next comes a line that contains integers n and k ( 1 <= n <= 2 cdot 10^5 , 0 <= k <= 10^9 ) -- the number of mines and the distance that hit by mines during the explosion, respectively. Then n lines follow, the i -th of which describes the x and y coordinates of the i -th mine and the time until its explosion ( -10^9 <= x, y <= 10^9 , 0 <= timer <= 10^9 ). It is guaranteed that all mines have different coordinates. It is guaranteed that the sum of the values n over all test cases in the test does not exceed 2 cdot 10^5 . Print t lines, each of the lines must contain the answer to the corresponding set of input data -- the minimum number of seconds it takes to explode all the mines. First example: Second example: '...