29189번 - Революция 다국어

Решающая битва Нео и Смита назначена на 19:00, но из-за сбоя системы Смит-Оракул не знает, сколько сейчас точно времени и поэтому опаздывает. Нео в это время решил поизучать оставшихся Смитов, стоящих в ряд.

Известно, что Агент Смит, превращая кого-либо в себя не меняет код полностью. Поэтому, изучая исходники любого Смита, можно сказать, был человек перед превращением мужчиной или женщиной. Нео вспомнил как тяжело на корабле, когда мужчин гораздо больше, чем женщин, и решил вычислить такой подотрезок, который, по мнению Нео, $k$-хороший. А Нео считает, что отрезок $k$-хороший, если он начинается со Смита-женщины и кончается Смитом-мужчиной и содержит внутри $(k-1)$-хороший подотрезок. $0$-хороший отрезок естесственно пустой (что же плохого, если никого нет). Мы не будем задаваться вопросом, откуда у Нео такие представления о хорошем (он же Избранный, ему видней), а попросим вас сказать, сколько же строго $k$-хороших отрезков. (более хорошие не считать: слишком хорошо уже плохо).

В самой первой строке написано число $m$ --- число тестов. В каждом тесте в первой строке заданы числа $n$ и $k$ ($2 \le n \le 100000$, $1 \le k \le n/2$), где $n$ --- количество агентов Смитов в ряду. Во второй строке заданы $n$ чисел $a_i$ ($0 \le a_i \le 1$), где $a_i = 0$, если Смит был женщиной, и $a_i = 1$, если Смит был мужчиной. Суммарное количесвто агентов во входном файле не превышает 100000

Для каждого теста выведите количество $k$-хороших отрезков.