Given an integer array nums and an integer k, determine the number of subarrays of nums where the greatest common divisor of all elements in the subarray equals k.

Note:
A subarray is defined as a contiguous sequence of elements within an array.
The greatest common divisor of a sequence of integers is the largest positive integer that divides each integer in the sequence without a remainder.

Constraints:

• $1 \leq$ nums.length $\leq 1000$

• $1 \leq$ nums[i], k $\leq 10^9$

Input: nums = [21]-List[int], k = 7-int
Output: 0-int
Explanation: No subarray has a greatest common divisor equal to 7.

Input: nums = [10, 15, 25]-List[int], k = 4-int
Output: 0-int
Explanation: No subarray has a greatest common divisor equal to 4.

Input: nums = [6, 18, 24, 30, 7, 42]-List[int], k = 6-int
Output: 7-int
Explanation: There are 7 contiguous subarrays whose greatest common divisor is 6.

Input: nums = [2, 3]-List[int], k = 10-int
Output: 0-int
Explanation: No subarray has a greatest common divisor equal to 10.

Now, let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Implement your solution in the following coding playground.