#1140 Sum of Sequence

88  1 s   128 MB  

Description

N개의 숫자로 이루어진 배열 L이 주어졌을 때, 이 N개의 숫자 중에 i번째부터 j번째까지의 배열을 전체 배열 L의 부분배열이라고 한다. (1 ≤ i < j ≤ N)

가령 배열 L = { 1, 2, 3, 4, 5 } 가 존재할 때 { 1, 2, 3 } 이나 { 2, 3 }, { 3, 4, 5 } 은 { 1, 2, 3, 4, 5 } 의 부분 배열이지만 { 1, 3, 5 }는 부분 배열이 아니다.

( L(1, 3) = { 1, 2, 3 }, L(2, 3) = { 2, 3 }, L(3, 5) = { 3, 4, 5 } )

N개의 숫자로 이루어진 배열 L과 2 이상의 정수 K가 주어질 때 부분배열 내 모든 정수의 합이 K의 배수가 되는 경우의 수를 모두 찾아 출력하는 프로그램을 작성하라. 배열의 크기가 1인 부분배열과 전체 배열 L도 부분배열이라고 인정한다. ( 예 – { 1 }, { 3 } 등등… )

Input

맨 처음 테스트 케이스의 개수 T( 1 <= T <= 50)가 주어진다. 그 다음 T의 크기만큼 배열 L의 크기 N과 K가 주어진다. ( 1 <= N <= 100, 2 <= K <= 10 ) 그 다음 N의 크기만큼 배열 L의 원소 Li가 주어진다. (1 <= Li <= 10000)


Output

배열 내 합이 K의 배수인 부분배열의 수를 출력한다.


Sample Input

Sample Output

2
3 4
1 2 3
5 3
1 2 3 4 5
0
7

HINT

두 번째 Case에서 합이 3의 배수가 되는 부분배열은

{ 3 }, { 1, 2 }, { 4, 5 }, { 1, 2, 3 }, { 2, 3, 4 }, { 3, 4, 5 }, { 1, 2, 3, 4, 5 } 로 총 7가지이다.

Source

2010 Ajou University Programming Contest