Kevin喜欢零(困难版本)

题号：NC252712
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

本题分为简单版本和困难版本，二者唯一的区别是：简单版本有序列 $a$ 所有元素乘积 $\leq 10^{18}$ 的限制，困难版本没有。

氧气少年最近喜欢上了零。

给出一个长度为 $n(1\leq n\leq 2\cdot 10^5)$ 的序列 $a$ $(1\leq a_i\leq 10^9)$ ，求这个序列中满足如下条件的连续子段 $[a_l\dots a_r]$ 的数量：

令 $x=a_l\cdot a_{l+1}\cdot a_{l+2}\dots a_r$ ，那么 $x$ 的末尾恰好有 $k(0\leq k\leq 10^9)$ 个零。

第一行包含一个整数 ，表示测试用例的组数。

对于每组测试用例：

第一行包含两个整数  和 ，表示序列的长度和题目中提到的后导零的数量；

第二行包含  个整数 ，表示该序列。

保证对于所有的测试用例， 的总和不超过 。

对于每组测试用例：

仅输出一行，包含一个整数，表示答案。

示例1

复制

2
5 3
125 1 8 1 1
1 0
6

复制

3
1