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 tồn tại các chỉ số ~i_1, i_2, \dots, i_k~ ~(1 \le i_1 < i_2 < \dots < i_k \le n)~ sao cho ~\overline{S_{i_1} S_{i_2} \dots S_{i_k}} = x~ và ~x~ không có chữ số ~0~ thừa ở đầu.

Input

Dòng đầu tiên ghi số test ~t~ ~(1 \le t \le 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 \le n \le 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.

Scoring

Sample Input 1

4
6
177013
3
555
10
0123456789
6
130505

Sample Output 1

6
3
17
38

Notes

Ở 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~