인경호의 징검다리

인경호에는 연못을 가로지르는 특별한 징검다리가 있다. 이 징검다리에는 다음 성질이 있다.

1. 돌은 모두 $N$개이고, 놓인 순서대로 1번부터 $N$번까지 번호가 붙어 있다. 각 돌에는 양의 정수가 하나씩 적혀 있다.
2. 돌의 강도는 모두 $K$로 같고, $K$를 넘는 힘을 받으면 부서진다.
3. 매일 자정이 되면 돌의 개수 $N$, 돌의 강도 $K$, 각 돌에 적힌 수가 새로 바뀐다.

매일 같은 길로 등교하는 것이 지루했던 송이는 이 징검다리로 놀이를 하며 등교한다. 1번 돌에서 시작해 번호가 커지는 순서로 돌을 몇 개 밟고 $N$번 돌에서 끝낸 다음, 밟은 돌에 적힌 수를 모두 곱한다. 1번 돌과 $N$번 돌에 적힌 수도 곱에 들어간다. 놀이의 목표는 이 곱의 trailing zero를 가장 적게 만드는 것이다. trailing zero는 가장 낮은 자릿수부터 이어지는 0의 개수를 뜻한다. 10, 10100, 20151128의 trailing zero는 각각 1, 2, 0이다.

1번 돌에서 $N$번 돌까지 한 번에 뛰면 trailing zero를 쉽게 줄일 수 있다. 하지만 돌은 $K$를 넘는 힘을 받으면 부서지므로 언제나 그렇게 할 수는 없다. 돌에 가해지는 힘은 뛴 거리로 정해진다. $i$번 돌에서 $j$번 돌로 뛰면 $i$번 돌은 $j - i$의 힘을 받는다. 1번 돌에서 $N$번 돌까지 한 번에 뛰면 1번 돌이 받는 힘은 $N - 1$이 된다. 따라서 한 번에 뛸 수 있는 거리는 최대 $K$다.

아래 그림은 $N = 8$, $K = 2$인 경우다.

1번과 8번만 밟으면 곱이 $5 \times 3 = 15$가 되어 trailing zero는 0이다. 하지만 1번 돌이 받는 힘이 7이므로 $K = 2$에서는 불가능하다. 1번, 2번, 4번, 5번, 7번, 8번을 차례로 밟으면 곱은 3000이고 trailing zero는 3이다. 1번, 3번, 4번, 6번, 8번을 차례로 밟으면 곱은 900이고 trailing zero는 2다. 이 경우가 최소이며, trailing zero를 2보다 작게 만드는 순서는 없다.

돌의 개수가 크게 늘어난 뒤로 송이는 최적의 순서를 직접 찾지 못하게 되었다. 징검다리의 상태가 주어질 때 trailing zero의 개수를 최소로 만드는 프로그램을 작성하자.

첫 줄에 송이가 등교하는 날의 수 $T$ ($1 \le T \le 20$)가 주어진다. 다음 줄부터 $T$개의 징검다리 정보가 각각 두 줄에 걸쳐 주어진다.

각 정보의 첫 줄에는 돌의 개수 $N$ ($2 \le N \le 100000$)과 돌의 강도 $K$ ($1 \le K \le 20$)가 공백으로 구분되어 주어진다. 둘째 줄에는 1번 돌부터 $N$번 돌까지 번호가 커지는 순서로 각 돌에 적힌 값 $S_i$ ($1 \le S_i \le 2^{31} - 1$)가 주어진다.

모든 날의 $N$을 더한 값은 200000을 넘지 않는다.

송이가 등교한 날마다 한 줄에 하나씩, 놀이를 최적으로 했을 때 얻을 수 있는 trailing zero의 개수를 출력한다. 놀이는 항상 1번 돌에서 시작해 $N$번 돌에서 끝나야 하고, 돌은 번호가 커지는 순서로 밟아야 한다. 곱하는 값에는 1번 돌과 $N$번 돌의 값도 들어간다. 놀이를 최적으로 한다는 것은 trailing zero를 가능한 한 적게 만든다는 뜻이다.