Kichik shaxzoda 🚀
Description
Kichik shaxzoda o'z planetasida yashaydi. Uning malikasi esa boshqa planetada. Kichik shaxzoda malikaning havfda ekanidan habar topadi va uni qutqarishga yo'lga otlanadi. Afsuski uning raketasi unchalik kuchli emas. Shuning uchun u yo'lda iloji boricha kamro planeta kesib o'tishiga to'g'ri keladi. Quyidagi harita Samon Yo'li galaktikasini Kichik Shaxzoda sayohat qiladigan qismini ko'rsatadi.
Qizil chiziq shaxzodani planeta hududiga eng kam kirish/chiqish orqali yetish yo'lini anglatadi. Aylanalar planetalar chegaralarini. Eng kam kirish/chiqish bajariladigan yo'llar ko'p, lekin qay yo'l bilan bormasin kamida 3 marta planeta chegarasini kesib o'tishiga to'g'ri keladi.
Shaxzodaning va malikaning kordinatalari berilgan bo'lsa, shaxzoda necha marta planeta chegarasini kesib o'tishga majbur ekanini aniqlaydigan dastur tuzing (Masala shartida planetalar chegaralari ustma-ust tushmaydi va bir birini kesib o'tmaydi. Shuningdek, shaxzoda va malika kordinatalari hech qachon chegara ustida bo'lmaydi).
#Input
Birinchi qatortestcaselar soni T berilgan.
Keyingi qatordan boshlab, har birtestcasening birinchi qatorida shaxzoda
(x1,y1)(x1,y1) va malikaning (x2,y2)(x2,y2) kordinatalari berilgan.Testcasening ikkinchi qatorida planetar soni n berilgan.
Keyingi n ta qatorning har birida planeta markazi (cx,cy)(cx,cy) va radiusi r berilgan. (−1000≤x1,y1,x2,y2,cx,cy≤1000,1≤r,T≤1000,1≤n≤50)(−1000≤x1,y1,x2,y2,cx,cy≤1000,1≤r,T≤1000,1≤n≤50)
#Output
Har bir testcase uchun shaxzoda nechta planeta chegarasini kesib o'tishga majburligini alohida qatorlarda hop eting.