Cho một dãy số nguyên dương ~a~, đế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 hay dãy con đó trong dãy gốc là khác nhau.

Ví dụ:

• Với ~d = 4~, dãy (~2, 1, 2, 1, 4, 1~) có ~4~ dãy con thoả 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 thoả mãn

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 nhóm dòng tương ứng với một yêu cầu:

• Dòng đầu là hai số nguyên dương ~d~ và ~n~ (~d \le 10^6~, ~n \le 5 * 10^4~)

• Dòng thứ hai chứa ~n~ số nguyên dương biểu diễn dãy số

OUTPUT

~t~ dòng là kết quả của các test theo thứ tự

SAMPLE INPUT

1
2 4
1 1 1 1

SAMPLE OUTPUT

4

Giải thích: Các cặp (~i, j~) sau thoả mãn: (~1, 2~), (~2, 3~), (~3, 4~), (~1, 4~)