Xét xâu S độ dài không vượt quá 10¹⁸ chỉ gồm các ký tự ‘a’ đến ’z’ được mã hoá thành xâu SE (chỉ gồm các ký tự ‘a’ đến ‘z’ và ký tự ‘0’ đến ‘9’) như sau: Đi từ trái qua phải, mã hoá dãy các ký tự liên tiếp bằng nhau trong S thành ký tự đại diện và số lượng. Độ dài các xâu mã hoá không vượt quá 1000.

Ví dụ, xâu S=aaabbbbaaaaaaaaaaz thì SE=a3b4a10z1

Yêu cầu: Cho xâu S được mã hoá thành SE, đếm số lượng xâu khác nhau nhận được từ S bằng cách giữ nguyên hoặc xoá đi một số ký tự (đưa ra kết quả mod 111539786)
Ví dụ: SE=a10 thì số lượng các xâu khác nhau nhận được từ S là 10

Input

- Dòng đầu chứa số T là số bộ dữ liệu (T<=1000);
- T dòng sau, mỗi dòng chứa xâu SE là mã hóa của S.

Output

- Gồm T dòng, mỗi dòng là kết quả tương ứng với dữ liệu vào.