- Practice
- Mathematics
- Combinatorics
- Consecutive Subsequences

# Consecutive Subsequences

# Consecutive Subsequences

Jigar got a sequence of **n** positive integers as his birthday present! He likes consecutive subsequences whose sum is divisible by **k**. He asks you to write a program to count them for him.

**Input Format**

The first line contains **T**, the number of testcases.

**T** testcases follow. Each testcase consists of 2 lines.

The first line contains **n** and **k** separated by a single space.

And the second line contains **n** space separated integers.

**Output Format**

For each test case, output the number of consecutive subsequenences whose sum is divisible by **k** in a newline.

**Constraints**

1 ≤ T ≤ 20

1 ≤ n ≤ 10^{6}

1 ≤ k ≤ 100

1 ≤ a[i] ≤ 10^{4}

**Sample Input**

2 5 3 1 2 3 4 1 6 2 1 2 1 2 1 2

**Sample Output**

4 9

**Explanation**

For

```
1 2 3 4 1
```

there exists, 4 subsequences whose sum is divisible by 3, they are

```
3
1 2
1 2 3
2 3 4
```

For

```
1 2 1 2 1 2
```

there exists, 9 subsequences whose sum is divisible by 2, they are

```
2
2
2
1 2 1
1 2 1
1 2 1 2
2 1 2 1
1 2 1 2
2 1 2 1 2
```