SPRIME

Một số nguyên dương được gọi là số "đẹp" nếu tổng các chữ số trong hệ thập phân của nó là một số nguyên tố. Ví dụ: 1112 là số đẹp (vì 1+1+1+2=5), còn 2025 không phải là số đẹp (vì 2+0+2+5=9).

Xâu S được tạo thành bằng cách ghép nối tất cả các số đẹp <= 10^15 theo thứ tự tăng dần: 2357111214162021...

Cho T bộ dữ liệu. Mỗi bộ dữ liệu gồm một xâu ký tự số x có độ dài <= 100. Dữ liệu đảm bảo x xuất hiện dưới dạng một xâu con liên tiếp trong S. Hãy tìm vị trí (chỉ số bắt đầu từ 1) của lần xuất hiện đầu tiên của x trong S.

Đầu vào:

• Dòng đầu tiên chứa số nguyên T (1 <= T <= 100) — số lượng bộ dữ liệu.
• T dòng tiếp theo, mỗi dòng chứa một xâu ký tự x. Dữ liệu đảm bảo x là một xâu con liên tiếp của S.

Đầu ra:

• Với mỗi xâu x, in ra một số nguyên duy nhất là vị trí của lần xuất hiện đầu tiên của x trong S.

Ví dụ 1:

Đầu vào:

1
2

Đầu ra:

1

Ví dụ 2:

Đầu vào:

1
21356213

Đầu ra:

28495

Giới hạn:

• T <= 100
• Độ dài của xâu x <= 100