- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
دور میز دایرهای ناهار در شرکت میلی تعدادی کیسه شامل سکه طلا داریم. این کیسهها ممکن است حاوی تعدادی سکه طلا و تعدادی سکه تقلبی باشند. هر کیسه یک عدد به عنوان ارزش دارد که تعداد سکههای طلا آن را نشان میدهد. به دلیل اینکه طلا از اهمیت زیادی برای این شرکت برخوردار است، در صورتی که کیسهای حاوی سکه قلابی باشد به ازای هر سکه قلابی یک ارزش منفی میگیرد. پس ارزش هر کیسه برابر است با تعداد سکههای طلا آن منهای تعداد سکههای قلابی آن.
میلی برای آشمز یک چالش تعریف کرده که آیا میتواند با تکرار یک عملیات روی میز، ارزش تمام کیسهها را صفر کند؟ او در هر عملیات میتواند یک کیسه انتخاب کند و داخل آن یک سکه تقلبی بیندازد و در کیسه بعدی (در جهت عقربههای ساعت) یک سکه طلا بیندازد. او از شما میخواهد کمترین تعداد عملیات را محاسبه کنید تا بتواند ارزش تمام کیسهها را صفر کند. تضمین میشود که همه تست کیس ها راه حل دارند.
ورودی
در خط اول ورودی تعداد تستکیس ها \(T\) میآید.
در خط اول هر تستکیس عدد \(n\) ، تعداد کیسهها میآید.
در خط دوم هر تستکیس، از یکی از کیسهها شروع میکنیم و به ترتیب در جهت عقربههای ساعت ارزش کیسهها ورودی داده میشود (کیسه بعد از آخرین کیسه، همان اولین کیسه است). \(a_1, a_2, \ldots, a_n\)
\[1 \le T \le 10^4\] \[1 \le n \le 2 \times 10^5\] \[-10^9 \le a_i \le 10^9\]
تضمین میشود جمع تعداد کیسهها در همه تستکیسها حداکثر \(2 \times 10^5\) میباشد.
خروجی
جواب هر تستکیس را در یک خط جداگانه خروجی دهید.
مثال
ورودی نمونه ۱
3
2
2 -2
4
4 0 -2 -2
5
1 0 -2 3 -2
خروجی نمونه ۱
2
10
8