나누어떨어지는 연속 부분 수열

양의 정수로 이루어진 수열이 주어진다. 이 수열의 연속한 부분 수열 중에서 원소들의 합이 정수 $d$로 나누어떨어지는 것이 몇 개인지 세는 프로그램을 작성하시오.

예를 들어 수열 $2, 1, 2, 1, 1, 2, 1, 2$에서 합이 $4$로 나누어떨어지는 연속 부분 수열은 모두 $6$개이다. 구체적으로 위치 구간(1부터 시작하며 양 끝을 포함) $[1, 8]$, $[2, 4]$, $[2, 7]$, $[3, 5]$, $[4, 6]$, $[5, 7]$에 해당하는 부분 수열의 합이 각각 $4$의 배수이다.

첫째 줄에 테스트 케이스의 개수 $c$가 주어진다 ($1 \le c \le 200$). 각 테스트 케이스는 두 줄로 이루어진다.

각 테스트 케이스의 첫째 줄에는 나눗셈의 기준이 되는 정수 $d$ ($1 \le d \le 1{,}000{,}000$)와 수열의 길이 $n$ ($1 \le n \le 50{,}000$)이 공백으로 구분되어 주어진다. 둘째 줄에는 수열의 원소 $n$개가 공백으로 구분되어 주어지며, 각 원소는 $1$ 이상 $1{,}000{,}000{,}000$ 이하의 정수이다.

각 테스트 케이스마다 합이 $d$로 나누어떨어지는 연속 부분 수열의 개수를 한 줄에 하나씩 출력한다.