Count of Contiguous Subarrays with Product Less Than K

You are given an array of positive integers and an integer k. Your task is to determine the number of contiguous subarrays such that the product of all the elements in the subarray is less than k. This problem can be efficiently solved using a sliding window approach.

Explanation: For each subarray, if the product of the elements is less than k, it contributes to the count. When the product becomes equal to or exceeds k, the window is adjusted by moving the left pointer until the product falls below k again.

Note: If k is less than or equal to 1, the answer is 0 since no subarray can have a product less than k under these conditions.

Mathematically, if you denote cnt as the total count, it can be computed by summing up (right - left + 1) at each step after adjusting the window.

inputFormat

The input is read from standard input (stdin) and is structured as follows:

1. The first line contains an integer T, the number of test cases.
2. For each test case, the first line contains an integer n, representing the number of elements in the array.
3. The second line contains n space-separated positive integers, the elements of the array.
4. The third line contains an integer k.

outputFormat

For each test case, output a single integer representing the number of contiguous subarrays where the product of all elements is less than k. The output for each test case should be printed on a new line to standard output (stdout).

## sample

2
4
10 5 2 6
100
3
1 2 3
0

8
0

</p>