Stepping Stones on Ingyeong Lake

A special line of stepping stones crosses the pond at Ingyeong Lake. The stones have the following properties.

1. There are $N$ stones, numbered 1 to $N$ in the order they are laid out. Each stone has one positive integer written on it.
2. Every stone has the same strength $K$, and a stone breaks when it takes a force greater than $K$.
3. At midnight every day the stone count $N$, the strength $K$, and the number written on each stone all change.

Songi was bored of walking the same way to school every day, so she turned the stepping stones into a game. She starts on stone 1, steps on some stones in increasing order of their numbers, finishes on stone $N$, and multiplies together the numbers written on the stones she stepped on. The numbers on stone 1 and stone $N$ are part of the product. The goal of the game is to make the number of trailing zeros of that product as small as possible. Trailing zeros are the zeros that run without a break from the last digit upward. The numbers 10, 10100 and 20151128 have 1, 2 and 0 trailing zeros.

Jumping from stone 1 straight to stone $N$ would make the trailing zeros easy to avoid, but a stone breaks under a force greater than $K$, so that jump is not always allowed. The force on a stone is the length of the jump taken from it. Jumping from stone $i$ to stone $j$ puts a force of $j - i$ on stone $i$. Jumping from stone 1 straight to stone $N$ puts a force of $N - 1$ on stone 1. A single jump therefore covers a distance of at most $K$.

The picture below shows the case $N = 8$, $K = 2$.

Stepping only on stone 1 and stone 8 gives the product $5 \times 3 = 15$ with 0 trailing zeros, but stone 1 would take a force of 7, which is impossible when $K = 2$. Stepping on stones 1, 2, 4, 5, 7 and 8 in that order gives 3000, which has 3 trailing zeros. Stepping on stones 1, 3, 4, 6 and 8 gives 900, which has 2 trailing zeros. That is the smallest possible, and no order produces fewer than 2 trailing zeros.

Once the stone count grew large, Songi could no longer find the best order by hand. Given the state of the stepping stones, write a program that finds the smallest possible number of trailing zeros.

The first line contains the number of school days $T$ ($1 \le T \le 20$). The description of $T$ lines of stepping stones follows, two lines each.

The first line of a description contains the stone count $N$ ($2 \le N \le 100000$) and the stone strength $K$ ($1 \le K \le 20$), separated by a space. The second line contains the values $S_i$ ($1 \le S_i \le 2^{31} - 1$) written on stone 1 through stone $N$, in increasing order of stone number.

The sum of $N$ over all days is at most 200000.

For each school day, print on its own line the number of trailing zeros Songi gets when she plays the game optimally. The game always starts on stone 1 and ends on stone $N$, and the stones must be stepped on in increasing order of their numbers. The values on stone 1 and stone $N$ are part of the product. Playing optimally means making the number of trailing zeros as small as possible.