Start: 2025-01-06 00:00:00

25金华第二届信息联赛复盘

End: 2025-01-18 00:00:00
Now  2025-09-14 00:14:30  类型: IOI  状态: Ended 

P2. 区间积
Description

给定一个长度为n的数组a_1,a_2,\dots a_n,满足所有数都是非负整数。

a种有多少个非空子区间,满足区间种所有数的积\geq VV也是给定的!


Input

第一行一个正整数T,表示有T组数;

每组数据第一行两个整数n,V;

接下来一行n个整数,第i个数字是a_i;


Output

T行,每行一个数字表示区间内大于V的个数

Examples

Input

1
3 7
2 3 4

Output

2

Input

1 
13 5 
1 2 3 1 2 3 0 1 2 3 1 2 3

Output

24
Hint

样例说明:

存在两个区间的积是大于7的:[2,3,4],[3,4]

数据范围:

20%的数据:n\leq 100

60%的数据:n\leq 1000

100%的数据:n\leq 10^5,1\leq t \leq 5,0\leq a_i,V\leq 10^9


Submit

题目参数
Time Limit 1 second
Memory Limit 256 MB
Submit