Cho dãy S gồm n chữ số từ 0 đến 9. Hãy tìm số lượng số tự nhiên chia hết cho 5 khác nhau là dãy con của S. Vì kết quả rất lớn, nên lấy số dư khi chia cho ~10^9+7~. Một số tự nhiên x là dãy con của S nếu ta có thể xóa một số chữ số của S thì thu được x (không có chữ số 0 vô nghĩa ở đầu).

INPUT

Dòng đầu tiên ghi số test t (1 ≤ t ≤ ~10^6~). Tiếp theo là mô tả của t test. Dòng đầu tiên của test ghi một số nguyên dương n (1 ≤ n ≤ ~10^6~).

Dòng tiếp theo ghi dãy S gồm n chữ số từ 0 đến 9.

Dữ liệu đảm bảo tổng n của mọi test không vượt quá ~10^6~.

OUTPUT

Với mỗi testcase, in ra đáp án trên một dòng.

GIỚI HẠN

• 30% số test thỏa mãn 1 ≤ t ≤ ~10^4~, 1 ≤ n ≤ 7

• 30% số test khác thỏa mãn không tồn tại chữ số 0 trong S

• 40% số test còn lại không có điều kiện gì thêm.

Ví dụ:

INPUT

4
6
177013
3
555
10
0123456789
6
130505

OUTPUT

6
3
17
38

Giải thích ví dụ:

Ở test 1, có 6 số thoả mãn điều kiện là: 0, 10, 70, 170, 770, 1770

Ở test 2, có 3 số thoả mãn điều kiện là: 5, 55, 555