Có ba con rùa nằm trên một đường thẳng được mô tả như là trục số Ox. Ban đầu, con thứ nhất ở vị trí ~x = a~, con thứ hai ở vị trí ~x = b~ và con thứ ba ở vị trí ~x = c~. Đôi khi, một số con rùa có thể ở cùng một vị trí.

Trong một bước di chuyển, mỗi con rùa có thể di chuyển đến vị trí ~x - 1~ (đi sang trái) hoặc là đến vị trí ~x + 1~ (đi sang phải) hoặc giữ nguyên vị trí.

Biết rằng ba con rùa đều muốn đến gần nhau hơn với không quá một bước di chuyển. Hãy tính tổng khoảng cách nhỏ nhất có thể giữa mỗi cặp rùa với giả định cả ba con rùa đều di chuyển tối ưu. Bạn phải trả lời ~q~ truy vấn độc lập.

Yêu cầu: Tính tổng khoảng cách nhỏ nhất giữa các cặp rùa sau khi mỗi con di chuyển tối đa một bước.

Input

• Dòng đầu tiên chứa số nguyên ~q~ (~1 \le q \le 10^4~) là số truy vấn.
• Tiếp theo là ~q~ truy vấn, mỗi truy vấn một dòng chứa lần lượt ba số nguyên ~a, b, c~ viết cách nhau một dấu cách.

Output

• In ra ~q~ dòng, dòng thứ ~i~ ghi một số nguyên duy nhất là đáp án tương ứng với truy vấn thứ ~i~ từ đầu vào.

Một số nguyên dương được gọi là số PDS nếu tích của các chữ số của nó chia hết cho tổng các chữ số của nó. Gọi ~PDS(N)~ là số PDS thứ ~N~ (Được lập chỉ mục từ 1).

Yêu cầu: Xác định số ~PDS(N)~.

Input

• Chứa một số nguyên dương ~N~ (~N \le 10^9~).

Output

• Ghi ra một số nguyên là số ~PDS(N)~.

Cho một dãy số nguyên, đếm số lượng dãy con liên tiếp có tổng là số nguyên tố. 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ụ dãy ~2, 3, 4~; có 4 dãy con thỏa mãn là ~(2), (3), (2,3), (3,4)~.

Yêu cầu: Đếm số lượng dãy con liên tiếp có tổng là số nguyên tố.

Input

• Dòng đầu chứa một số nguyên dương ~N~ (~N \le 10^4~).
• Dòng thứ 2 chứa ~N~ số nguyên dương ~a_1, a_2, \dots, a_N~ (~a_i \le 10^3~).

Output

• Ghi ra kết quả của bài toán.

Cho dãy số ~A~ gồm ~n~ số nguyên dương ~a_1, a_2, \dots, a_n~ và số nguyên ~k~. Ta gọi dãy con gồm các số hạng ở vị trí liên tiếp ~a_i, a_{i+1}, \dots, a_j~ là dãy số đẹp thỏa mãn:

• Trong dãy con ~a_i, a_{i+1}, \dots, a_j~ có ít nhất một số chẵn và ít nhất một số lẻ.
• Gọi ~x~ là tổng các số hạng chẵn, ~y~ là tổng các số hạng lẻ trong dãy con ~a_i, a_{i+1}, \dots, a_j~ thì ~0 \le x - y \le k~.

Yêu cầu: Tìm số lượng dãy con các số hạng liên tiếp của dãy ~A~ là dãy số đẹp.

Input

• Dòng 1: Ghi hai số nguyên dương ~n, k~.
• Dòng 2: Ghi ~n~ số nguyên ~a_1, a_2, \dots, a_n~ (~1 \le a_i \le 10^6~).

Output

• Ghi ra một số nguyên là số lượng dãy con của ~A~ là dãy số đẹp.

Cho một dãy gồm ~N~ số nguyên ~a_1, a_2, \dots, a_N~ và một số nguyên dương ~K~. Ta có biểu thức: ~? a_1 ? a_2 \dots ? a_N = X~ Trong đó ta có thể thay thế dấu ‘?’ bằng các phép toán ‘+’ hoặc ‘-’. Hãy đếm xem có tất cả bao nhiêu cách thay dấu khác nhau để ~X~ chia hết cho ~K~. Hai cách thay dấu gọi là khác nhau nếu tồn tại một vị trí mà ở đó dấu ở cách này khác dấu ở cách kia.

Yêu cầu: Đếm số cách thay dấu sao cho kết quả chia hết cho ~K~, lấy modulo cho ~10^9 + 7~.

Input

• Dòng đầu tiên gồm 2 số nguyên dương ~N, K~.
• Dòng thứ hai gồm ~N~ số nguyên dương ~a_1, a_2, \dots, a_N~ (~a_i \le 10^9~).

Output

• Ghi ra số cách thay dấu lấy modulo cho ~10^9 + 7~.