Description

给你一个长度为 $n$ 的整数数组 $nums$ 和一个整数 $k(0<=k<=10^9)$，请你输出子数组内所有元素的乘积严格小于 $k$ 的连续子数组的数目。

子数组是指数组中连续的一段数据。如在数组[$2,3,5$]中，子数组有[$2,3,5$],[$2,3$],[$3,5$],[$2$],[$3$],[$5$]

Input Format

有 $T$ 组样例。

第一行输入一个整数 $T$。

每组样例描述如下：

第一行输入两个正整数 $n(1<n<=3*10^4)$和 $k(0<=k<=10^9)$，对于单个评测数据题目保证 $n$ 的总和不超过 $3*10^6$。

接下来 $1$ 行输入 $n$ 个数，描述数组 $nums$ ，其中 $0<nums[i]<=1000$。

Output Format

输出 $T$ 行。

每行输出对应样例的答案，即子数组内所有元素的乘积严格小于 $k$ 的连续子数组的数目。

1
4 100
10 5 2 6

8

Hint

$8$ 个乘积小于 $100$ 的子数组分别为：$[10]、[5]、[2]、[6]、[10,5]、[5,2]、[2,6]、[5,2,6]$。注意的是 $[10,5,2]$ 并不是乘积小于 $100$ 的子数组。

Source

1816 Online Judge 10.100.0.232