시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 193 77 63 50.806%

문제

양의 정수로 이루어진 수열이 주어졌을 때, 연속하는 부분 수열의 합이 d로 나누어 떨어지는 것의 개수를 구하는 프로그램을 작성하시오.

예를 들어, 아래와 같은 수열의 부분 수열 중 4로 나누어 떨어지는 것의 개수는 6개이다.

2, 1, 2, 1, 1, 2, 1, 2

다음과 같은 부분 수열은 합이 4로 나누어 떨어진다. 1~8, 2~4, 2~7, 3~5, 4~6, 5~7번째

입력

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

테스트 케이스의 첫째 줄에는 d(1 ≤ d ≤ 1,000,000)와 수열의 크기 n(1 ≤ n ≤ 50,000)이 주어진다. 다음 줄에는 수열의 원소가 주어진다. 각 숫자는 1보다 크거나 같고, 1,000,000,000보다 작거나 같은 정수이다.

출력

각 테스트 케이스에 대해서, 주어진 수열의 연속하는 부분 수열의 합이 d로 나누어 떨어지는 것의 개수를 출력한다.

예제 입력 1

2
7 3
1 2 3
4 8
2 1 2 1 1 2 1 2

예제 출력 1

0
6
W3sicHJvYmxlbV9pZCI6IjM2NzMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIwOThcdWIyMGMgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWJkODBcdWJkODQgXHVjMjE4XHVjNWY0IiwiZGVzY3JpcHRpb24iOiI8cD5cclxuXHRcdWM1OTFcdWM3NTggXHVjODE1XHVjMjE4XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNCBcdWMyMThcdWM1ZjRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVjNWYwXHVjMThkXHVkNTU4XHViMjk0IFx1YmQ4MFx1YmQ4NCBcdWMyMThcdWM1ZjRcdWM3NTggXHVkNTY5XHVjNzc0IGRcdWI4NWMgXHViMDk4XHViMjA0XHVjNWI0IFx1YjVhOFx1YzViNFx1YzljMFx1YjI5NCBcdWFjODNcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCBcdWM1NDRcdWI3OThcdWM2NDAgXHVhYzE5XHVjNzQwIFx1YzIxOFx1YzVmNFx1Yzc1OCBcdWJkODBcdWJkODQgXHVjMjE4XHVjNWY0IFx1YzkxMSA0XHViODVjIFx1YjA5OFx1YjIwNFx1YzViNCBcdWI1YThcdWM1YjRcdWM5YzBcdWIyOTQgXHVhYzgzXHVjNzU4IFx1YWMxY1x1YzIxOFx1YjI5NCA2XHVhYzFjXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHQyLCAxLCAyLCAxLCAxLCAyLCAxLCAyPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NDAgXHViZDgwXHViZDg0IFx1YzIxOFx1YzVmNFx1Yzc0MCBcdWQ1NjlcdWM3NzQgNFx1Yjg1YyBcdWIwOThcdWIyMDRcdWM1YjQgXHViNWE4XHVjNWI0XHVjOWM0XHViMmU0LiAxfjgsIDJ+NCwgMn43LCAzfjUsIDR+NiwgNX43XHViYzg4XHVjOWY4PFwvcD5cclxuIiwiaW5wdXQiOiJcclxuPHA+XHJcblx0XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YWMxY1x1YzIxOCBjXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBjICZsZTsgMjAwKSBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBcdWI0NTAgXHVjOTA0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBkKDEgJmxlOyBkICZsZTsgMSwwMDAsMDAwKVx1YzY0MCBcdWMyMThcdWM1ZjRcdWM3NTggXHVkMDZjXHVhZTMwIG4oMSAmbGU7IG4gJmxlOyA1MCwwMDApXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViMmU0XHVjNzRjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWMyMThcdWM1ZjRcdWM3NTggXHVjNmQwXHVjMThjXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIFx1YzIyYlx1Yzc5MFx1YjI5NCAxXHViY2Y0XHViMmU0IFx1ZDA2Y1x1YWM3MFx1YjA5OCBcdWFjMTlcdWFjZTAsIDEsMDAwLDAwMCwwMDBcdWJjZjRcdWIyZTQgXHVjNzkxXHVhYzcwXHViMDk4IFx1YWMxOVx1Yzc0MCBcdWM4MTVcdWMyMThcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHJcblx0XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjLCBcdWM4ZmNcdWM1YjRcdWM5YzQgXHVjMjE4XHVjNWY0XHVjNzU4IFx1YzVmMFx1YzE4ZFx1ZDU1OFx1YjI5NCBcdWJkODBcdWJkODQgXHVjMjE4XHVjNWY0XHVjNzU4IFx1ZDU2OVx1Yzc3NCBkXHViODVjIFx1YjA5OFx1YjIwNFx1YzViNCBcdWI1YThcdWM1YjRcdWM5YzBcdWIyOTQgXHVhYzgzXHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMzY3MyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkRpdmlzaWJsZSBTdWJzZXF1ZW5jZXMiLCJkZXNjcmlwdGlvbiI6IjxwPkdpdmVuIGEgc2VxdWVuY2Ugb2YgcG9zaXRpdmUgaW50ZWdlcnMsIGNvdW50IGFsbCBjb250aWd1b3VzIHN1YnNlcXVlbmNlcyAoc29tZXRpbWVzIGNhbGxlZCBzdWJzdHJpbmdzLCBpbiBjb250cmFzdCB0byBzdWJzZXF1ZW5jZXMsIHdoaWNoIG1heSBsZWF2ZSBvdXQgZWxlbWVudHMpIHRoZSBzdW0gb2Ygd2hpY2ggaXMgZGl2aXNpYmxlIGJ5IGEgZ2l2ZW4gbnVtYmVyLiBUaGVzZSBzdWJzZXF1ZW5jZXMgbWF5IG92ZXJsYXAuIEZvciBleGFtcGxlLCB0aGUgc2VxdWVuY2UgKHNlZSBzYW1wbGUgaW5wdXQpPFwvcD5cclxuXHJcbjxwPjIsMSwyLDEsMSwyLDEsMjxcL3A+XHJcblxyXG48cD5jb250YWlucyBzaXggY29udGlndW91cyBzdWJzZXF1ZW5jZXMgdGhlIHN1bSBvZiB3aGljaCBpcyBkaXZpc2libGUgYnkgZm91cjogdGhlIGZpcnN0IHRvIGVpZ2h0aCBudW1iZXIsIHRoZSBzZWNvbmQgdG8gZm91cnRoIG51bWJlciwgdGhlIHNlY29uZCB0byBzZXZlbnRoIG51bWJlciwgdGhlIHRoaXJkIHRvIGZpZnRoIG51bWJlciwgdGhlIGZvdXJ0aCB0byBzaXh0aCBudW1iZXIsIGFuZCB0aGUgZmlmdGggdG8gc2V2ZW50aCBudW1iZXIuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiB0aGUgaW5wdXQgY29uc2lzdHMgb2YgYW4gaW50ZWdlciBjICgxICZsZTsmbmJzcDtjJm5ic3A7JmxlOyZuYnNwOzIwMCksIHRoZSBudW1iZXIgb2YgdGVzdCBjYXNlcy4gVGhlbiBmb2xsb3cgdHdvIGxpbmVzIHBlciB0ZXN0IGNhc2UuPFwvcD5cclxuXHJcbjxwPkVhY2ggdGVzdCBjYXNlIHN0YXJ0cyB3aXRoIGEgbGluZSBjb25zaXN0aW5nIG9mIHR3byBpbnRlZ2VycyBkICgxICZsZTsgZCAmbGU7IDEsMDAwLDAwMCkgYW5kIG4gKDEgJmxlOyBuICZsZTsgNTAsMDAwKSwgdGhlIGRpdmlzb3Igb2YgdGhlIHN1bSBvZiB0aGUgc3Vic2VxdWVuY2VzIGFuZCB0aGUgbGVuZ3RoIG9mIHRoZSBzZXF1ZW5jZSwgcmVzcGVjdGl2ZWx5LiBUaGUgc2Vjb25kIGxpbmUgb2YgYSB0ZXN0IGNhc2UgY29udGFpbnMgdGhlIGVsZW1lbnRzIG9mIHRoZSBzZXF1ZW5jZSwgd2hpY2ggYXJlIGludGVnZXJzIGJldHdlZW4gMSBhbmQgMSAwMDAgMDAwIDAwMCwgaW5jbHVzaXZlbHkuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggdGVzdCBjYXNlLCBwcmludCBhIHNpbmdsZSBsaW5lIGNvbnNpc3Rpbmcgb2YgYSBzaW5nbGUgaW50ZWdlciwgdGhlIG51bWJlciBvZiBjb250aWd1b3VzIHN1YnNlcXVlbmNlcyB0aGUgc3VtIG9mIHdoaWNoIGlzIGRpdmlzaWJsZSBieSBkLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==