. Cho một tập các chữ số S và một số nguyên n, bạn phải tìm xem có bao nhiêu số nguyên có n chữ số, sao cho nó gồm các chữ số thuộc về tập S và giá trị tuyệt đối giữa hai chữ số liền kề không lớn hơn 2

Input

Dòng đầu tiền gồm số nguyên T (T<=300), biểu thị số test

Mỗi dòng tiếp theo gồm hai số nguyên m (1<=m<10) và n (1<=n<=10).

Dòng tiếp theo gồm m số nguyên (từ 1 tới 9), những số nguyên này tạo thành tập S nói trên, chúng phân biệt và được cho theo thứ tự giảm dần

Output

Với mỗi test, đưa ra số lượng các số có n chữ số thỏa mãn đề bài