Cho một số a và b. Ta tiến hành xây dựng số mới c bằng cách sử dụng lần lượt các chữ số của số số a từ trái sang phải. Ở mỗi lượt có thể chọn 2 bên trái hoặc phải số c (trừ lượt đầu tiên) để đặt chữ số hiện tại vào. Ví dụ số c đang là 38182, đang xét số 1 thì sau khi đặt vào bên trái sẽ trở thành 138182, tương tự bên phải sẽ là 381821. Số c mới được phép có số 0 xuất hiện ở đầu.

Số được gọi là đẹp nếu số đó không vượt quá số b. Hãy tính tổng các số đẹp được xây dựng theo cách trên, 2 số được gọi là khác nhau nếu cách xây dựng số đấy khác nhau, kể cả giá trị có bằng nhau.

Input:

• Dòng đầu tiên gồm số tự nhiên T ≤ 50 là số lượng test.

• Mỗi nhóm dòng tiếp theo gồm xâu a với |a| ≤ 500 chỉ gồm các chữ số là số tự nhiên b ≤ 10^500

Output:

• Với mỗi test in ra một số là tổng các số đẹp modulo 10^9 + 7.

Input:

1
1013
3000

Output:

3242