Masala #0327

Robolandiya mamlakatida sport dasturchilari orasida final musobaqasi bo’lib o’tmoqda. Bu final musobaqasiga eng kuchlilar ishtirok etishmoqda va ularning barchasi musobaqadagi barcha masalalarni ishlash kuchiga ega, va ular shunchalik kuchli tayyorgarlik ko’rishganki, har bir ishtirokchi har bir masalani aynan 1 minutda va aynan 1 urinishda ishlab tugatadi.

Barcha ishtirokchilar shunday xususiyatga ega ekanligidan ma’lumki eng kam jarima olgan ishtirokchi g’olib bo’ladi. Buni bilgan hay’at a’zolari jarima vaqtini hisoblashning o’zgacha bir usulini ishlab chiqishdi.

Musobaqadagi jami N ta masala uchun N ta elementdan iborat A to’plamni hosil qilishdi. i-masala uchun jarima vaqti i-masala ishlangan vaqtdagi A_i qiymatga teng. Bu to’plam har minutda o’zgarib turish xususiyatiga ega. Bu o’zgarishda to’plamning i-elementi j-minut yakunida (j+1)*A_i ga ortadi, ya’ni A_i=A_i+ (j+1)*A_i ga o’zgaradi.

Hay’at a’zolarining bunday qarorlarini bilmagan holda Bitboy musobaqadagi barcha masalani ishlagan holda olinishi mumkin bo’lgan eng kichik jarima vaqtini bilan 1-o’rinni egalladi. Sizning vazifangiz Bitboyning musobaqadagi jarima vaqtini hisoblashdan iborat.

Kirish faylining dastlabki satrida bitta butun son, T(1 ≤ T ≤ 10), testlar soni kiritiladi.

Har bir testing dastlabki satrida bitta butun son, N(1 ≤ N ≤ 10⁵) musobaqadagi masalalar soni, hamda ikkinchi satrida N ta butun son, hay’at a’zolari hosil qilgan A(1 ≤ A_i ≤ 10⁹) to’plam elementlari kiritiladi.

Har bir test uchun alohida qatorda bitta butun son, Bitboyning musobaqadagi jarima vaqtini 10⁹+7 ga bo’lgandagi qoldiqni chop eting.