# Kostomuksha and AESC MSU Codechef Solution | MARCH CHALLENGE Share:

Kostomuksha and AESC MSU Codechef Solution

A famous student of AESC MSU, as you know, comes from Kostomuksha. Kostomuksha has a popular game called Doka.

The essence of Doka is as follows:

You are given an array AA and an integer XX. You want to calculate how many subarrays of this array have a geometric mean of XX.

Formally, calculate the number of pairs of integers (L,R)(L,R) such that 1≤L≤R≤N1≤L≤R≤N andAL⋅AL+1⋅…⋅AR−−−−−−−−−−−−−−−√R−L+1=XAL⋅AL+1⋅…⋅ARR−L+1=X

### Input Format

• The first line of input contains an integer TT, denoting the number of test cases. The description of TT test cases follows.
• Each test case consists of two lines of input.
• The first line of each test case contains two space-separated integers N,XN,X — the size of the array AA and the required geometric mean.
• The second line of each test case contains NN space-separated integers A1,A2,…,ANA1,A2,…,AN.

### Output Format

For each test case, on a new line print the number of subarrays that satisfy the condition.

### Constraints

• 1≤T≤1031≤T≤103
• 1≤N≤2⋅1051≤N≤2⋅105
• 1≤X,Ai≤1091≤X,Ai≤109
• Sum of NN over all test cases does not exceed 2⋅1052⋅105.

Subtask #1 (100 points): Original constraints

### Sample Input 1

``````3
3 3
3 3 3
4 4
1 2 3 4
4 54
36 81 54 54
``````

### Sample Output 1

``````6
1
6
``````

### Explanation

Test case 11: Every subarray has a geometric mean of 33, and there are 66 subarrays in total so the answer is 66.

Test case 22: The only subarray with a geometric mean of 44 is the singleton array , obtained with L=R=4L=R=4.

Test case 33: The 66 pairs of (L,R)(L,R) which have a geometric mean of 5454 are:

• (1,2)(1,2), giving the subarray [36,81][36,81]
• (1,3)(1,3), giving the subarray [36,81,54][36,81,54]
• (1,4)(1,4), giving the subarray [36,81,54,54][36,81,54,54]
• (3,3)(3,3), giving the subarray 
• (3,4)(3,4), giving the subarray [54,54][54,54]
• (4,4)(4,4), giving the subarray