Laiko ribojimas: 3s

Atminties ribojimas: 64MB

Jei norite pateikti savo sprendimą - prisijunkite.

Ugnikalnis

Genadijus savo eilinį šeštadienį praleido universitete spręsdamas programavimo uždavinius. Baigęs spręsti jis išsiruošė namo, tačiau netikėtai išsiveržė netoliese esantis ugnikalnis! Išsigandęs Genadijus pradėjo galvoti, kaip jam greičiau nusigauti namo. Pirmoji jam iškilusi problema - nuo universiteto link namų eina vienas vienintelis kelias, kuris padengtas lavos duobėmis!

Genadijus žino, kad kelią tarp universiteto ir namų gali įsivaizduoti kaip stačiakampį, kurio apatinio kairiojo kampo koordinatė yra (0,0), o viršutinio dešiniojo kampo koordinatė yra (W,L). Universitetas yra apatinėje stačiakampio kraštinėje, o Genadijaus namai - viršutinėje. Todėl Genadijus gali pradėti savo kelionę namo bet kuriame apatinės kraštinės taške, o baigti - bet kuriame viršutinės kraštinės taške. Ant kelio yra atsiradę N lavos duobių, kurias galima vaizduoti apskritimais. i-osios duobės centras yra taške (x_i,y_i), o jos spindulys yra r_i. Lyg problemų ir taip nepakaktų, kai kurios duobės kertasi viena su kita, taip suformuodamos dar didesnes duobes.

Genadijui kilo geniali mintis - juk jis dabar yra prie universiteto, o čia juk pilna įvairios įrangos. Grįžęs į patalpas Genadijus rado aparatą, parduodantį anti-lavos kostiumus (tai visiškai įprastas dalykas universitete :)). Vienas kostiumas leidžia perplaukti vieną lavos duobę ir po to suyra nuo karščio. Žinoma, kostiumai nėra pigūs, tad Genadijus norėtų išleisti kuo mažiau pinigų, t.y. nusipirkti kiek įmanoma mažiau kostiumų. Dar kartą išbėgęs į lauką vaikinas iš akies susižymėjo informaciją apie duobes ir kelią, tad dabar jam belieka išsiaiškinti, kiek mažiausiai kostiumų reikia nusipirkti, kad galėtų saugiai grįžti namo. Padėkite jam tai padaryti!

Pastaba. Jei dvi duobės liečiasi viename taške, Genadijus negali praeiti per tą susilietimo tašką be kostiumo.

Pradiniai duomenys

Pirmoje eilutėje pateiktas vienas sveikasis skaičius t - testų skaičius (1\\leqt\\leq100). Toliau seka t testų aprašymų.

Kiekvienas testas prasideda eilute su trimis sveikaisiais skaičiais N, W ir L, reiškiančiais atitinkamai lavos duobių skaičių, kelio plotį bei kelio ilgį (1\\leqN\\leq1000,1\\leqW,L\\leq10^9).

Kiekvienoje iš toliau einančių N eilučių įrašyta po tris sveikuosius skaičius x_i, y_i ir r_i - i-osios duobės koordinatės ir spindulys (0\\leqx_i\\leqW,1\\leqy_i\\leqL-1,1\\leqr_i\\leq10^9).

Yra garantuota, kad nė viena duobė nesikerta nei su apatine, nei su viršutine stačiakampio kraštine.

Rezultatai

Kiekvienam testui jūsų programa turi išvesti vieną sveikąjį skaičių - minimalų kiekį anti-lavos kostiumų, kurį turi įsigyti Genadijus, kad galėtų grįžti namo.

Pavyzdžiai

Pradiniai duomenys Rezultatai 
2
1 6 10
3 4 3
1 6 10
3 4 2
 
1
0
 
1
5 5 18
4 2 1
2 12 3
4 6 2
2 6 1
1 7 1
 
2

Paaiškinimas

Pirmojo testo atvejai atrodo štai taip (linijomis pažymėtas galimas Genadijaus kelias - žalia linija reiškia judėjimą be kostiumo, o raudona - su. Galimų kelių yra ir daugiau, tai tik vienas iš jų):

Pirmojo testo pirmasis atvejis Pirmojo testo antrasis atvejis

Antrojo testo vienas iš galimų kelių atrodo taip:

Antrojo testo pavyzdys