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 ~S_{i_1}S_{i_2} \dots S_{i_k} = x~ và ~x~ không có chữ số 0 thừa ở đầu.

Yêu cầu: Tìm số lượng số tự nhiên chia hết cho 5 khác nhau là dãy con của ~S~.

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.

Sample Input 1

4 
6 
177013 
3 
555 
10 
0123456789 
6 
130505 

Sample Output 1

6 
3 
17 
38