Masala #0333

Bitboyning tug’ilgan kuniga N ta do’sti tashrif buyurgan, u o’z do’stlarini xursand qilish maqsadida do’stlariga konfetlar bermoqchi. Bitboyning o’zi ham xursand bo’lishi uchun esa uning kamida K ta do’stining cho’ntagi konfetdan to’lgan bo’lishi kerak.

Bitboyning konfet berish tartibi quyidagicha:

1. Agar kamida K ta do’stining cho’ntagi konfetdan to’lgan bo’lsa konfet berishni to’xtatadi;
2. Cho’ntagi hali to’lmagan barcha do’stiga 1 tadan konfet berib chiqadi va yana 1-tartibga qaytadi.

Bitboy xursand bo’lishi uchun kamida nechta konfet tarqatishi kerakligini aniqlang!

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

Har bir testning birinchi satrida bitta butun son, N(1 ≤ N ≤ 10⁵) Bitboy do’stlari soni kiritiladi, ikkinchi satrda N ta [1, 10⁵] oralig’idagi butun son, Bitboyning har bir do’sti cho’ntagining konfet sig’imi kiritiladi, uchinchi satrda bitta butun son, K(1 ≤ K ≤ N) soni kiritiladi.

Har bir test uchun alohida qatorda bitta butun son, Bitboy xursand bo’lishi uchun kamida nechta konfet tarqatishi kerakligini chop eting.