Cho dãy số gồm ~n~ phần tử và số nguyên ~m~. Nhiệm vụ của bạn là đếm số cách điền các dấu ~+~, ~-~ và ~*~ giữa các phần tử ~a_i~ và ~a_{i + 1}~ với ~i < n~ để tạo thành biểu thức có giá trị chia hết cho ~m~.

Input

Dòng đầu tiên chứa số nguyên ~t~ là số bộ test. Các dòng sau là ~t~ bộ test.

Mỗi bộ test bao gồm:

• Dòng đầu tiên chứa 2 số nguyên dương ~n~ và ~m~ (~2 \leq n \leq 10~, ~m \leq 10^9~).

• Dòng tiếp theo gồm ~n~ số nguyên là các phần tử của dãy ~a~ (~0 \leq a_i \leq 10^9~).

Output

Với mỗi bộ test, in ra số lượng biểu thức thỏa mãn.

Sample Input 1

1
4 2
5 5 5 9

Sample Output 1

14

Notes