Wstęp do programowania w C++

Całkiem niedawno zostałeś szczęśliwym posiadaczem własnego jachtu i właśnie planujesz pierwszy rejs. Masz zamiar przepłynąć prosty odcinek o długości n mil morskich. Obecnie Twój jacht jest zacumowany w porcie na 0 mili trasy. Miejscem docelowym jest port znajdujący się na n-tej mili szlaku. Planujesz dotrzeć do niego maksymalnie w przeciągu d dni, bo tylko na taki okres posiadasz prognozę pogody. Każdego dnia wiatr wieje w kierunku portu na 0 mili albo w kierunku portu na n-tej mili. Ponieważ pogoda bywa kapryśna zabrałeś ze sobą również silnik i b zbiorników paliwa. Spalając 1 zbiornik paliwa możesz przepłynąć, w ciągu 1 dnia, 1 milę morską w kierunku portu docelowego, niezależnie od kierunku wiatru. Jeżeli płyniemy nie wykorzystując silnika to w ciągu 1 dnia pokonujemy 1 milę morską, zgodnie z kierunkiem, w którym wieje. Oprócz portu startowego i docelowego na szlaku mogą znajdować się również inne przystanie. W każdym porcie możesz zacumować na dowolną liczbę dni.

Twoim zadaniem jest sprawdzenie czy da się dopłynąć do portu na n-tej mili w ciągu maksymalnie d dni, a jeżeli tak to po ilu dniach najwcześniej możesz się tam znaleźć.

Wejście

W pierwszej linii wejścia znajduje się jedna liczba całkowita t ∈ [1;10] określająca liczbę zestawów danych. W kolejnych liniach znajduje się t zestawów danych.

W pierwszej linii każdego zestawu danych znajdują się trzy liczby całkowite n ∈ [1;100], b ∈ [0;100] i d ∈ [n;100] opisane powyżej. W następnym wierszu znajduje się n + 1 cyfr 0 lub 1 określających czy na kolejnych kilometrach od 0 do n znajduje się port. 1 oznacza port, 0 oznacza brak portu. Gwarantujemy, że pierwsza i ostatnia cyfra tego wyrazu, odpowiednio port na 0 mili i port na n-tej mili, zawsze będą 1. W ostatniej linii każdego zestawu danych znajduje się wyraz o długości d składający się z cyfr 0 lub 1 określający prognozę pogody na d dni. Cyfra 0 oznacza, że wiatr wieje w kierunku portu na n-tej mili zaś cyfra 1, że wiatr wieje w kierunku portu na 0 mili.

Wyjście

Dla każdego zestawu danych należy w osobnej linii wypisać minimalną liczbę dni, po upływie której możemy dotrzeć do przystani docelowej albo 0 jeżeli nie jest możliwe dotarcie do portu na n-tej mili w przeciągu d dni.

Przykład

Wejście:

1
2 1 4
101
1100

Wyjście:

3

Wyjaśnienie do przykładu:

Pierwszego dnia zostajemy w porcie na 0 mili. Drugiego dnia wypływamy i zużywając 1 zbiornik paliwa dopływamy do 1 mili. Trzeciego dnia płyniemy z wiatrem, pokonujemy ostatnią milę i dopływamy do portu docelowego.