Cho một dãy số nguyên dương, đếm số lượng dãy con liên tiếp có tổng chia hết cho ~d~. Hai dãy con được gọi là khác nhau nếu ít nhất một trong hai điểm đầu hoặc điểm cuối hai dãy con đó trong dãy đã cho là khác nhau.

Ví dụ với ~d = 4~, dãy ~(2, 1, 2, 1, 4, 1)~ có 4 dãy con thỏa mãn là ~(1, 2, 1)~, ~(1, 2, 1, 4)~, ~(4)~, ~(2, 1, 4, 1)~. Với ~d = 2~, dãy ~1, 1, 1, 1~ có 4 dãy con thỏa mãn.

Yêu cầu: Hãy đếm số lượng dãy con liên tiếp có tổng chia hết cho ~d~.

Input

• Dòng đầu tiên là số ~T~ – số lượng test (~T \le 100~).
• ~T~ nhóm dòng tiếp theo, mỗi dòng tương ứng một yêu cầu:
  • Dòng đầu là 2 số nguyên dương ~d~ và ~N~ (~d \le 10^6, N \le 5 \times 10^4~).
  • Dòng thứ 2 chứa ~N~ số nguyên biểu diễn dãy số.

Output

• Ghi ra kết quả các test tương ứng theo thứ tự.

Chú ý: 50% số test có ~N \le 1000~.

Sample Input 1

1
4 6
2 1 2 1 4 1 

Sample Output 1

4