1. Quiz

Вікторина (Quiz) (старша ліга)

Гноми-велетні вирішили взяти участь у чемпіонаті гри «Що? Де? Коли?». Чемпіонат складається з t турів. Кожен тур містить деяку кількість питань. Серія питань – це підпослідовність питань одного туру від l-ого до r-ого включно, причому l ≤ r і підпослідовність неперервна (беруться до уваги всі підряд питання від l-ого до r-ого). Гноми будуть вважати серію питань вдалою, якщо вони дадуть відповіді не менш, ніж на q відсотків питань з цієї серії. Для підняття настрою команди, знайдіть для кожного туру кількість вдалих серій.

Формат введення-виведення:

Програма Quiz зчитує з клавіатури (стандартного пристрою введення) число t – кількість турів у чемпіонаті, 1 ≤ t ≤ 10. У наступних t рядках знаходиться інформація про кожен з турів у такому вигляді: n q a₁...a_n, 0 ≤ q ≤ 100. a_i =  може бути 0, якщо команда не відповіла на i питання, або ж 1 в іншому випадку. Крім того, усього на чемпіонаті було задано не більш, ніж 500000 питань. Усі числа вхідних даних цілі.  Програма Quiz виводить на екран (стандартний пристрій виведення) рівно t чисел в один рядок через пробіл: i-те число дорівнює кількості вдалих серій питань у i-ому турі.

Система оцінки.70% балів припадатиме на тести, в яких q_i = 50.

Приклад вхідних та вихідних даних

Введення                                        Виведення

2

10 50 1 0 1 0 1 1 0 0 0 1                    32 4

5 50 1 0 0 0 1