{"code":"mult2019","name":"Multiple of 2019","description":"Bạn được cho một xâu $S$ gồm các chữ số từ $1$ đến $9$.\r\n\r\nNhiệm vụ của bạn là đếm số cặp số $(i,j)$ ($1 \\leq i \\leq j \\leq |S|$) thỏa mãn điều kiện như sau: Trong hệ cơ số thập phân, các chữ số từ $i$ đến $j$ trên xâu $S$ tạo thành một số chia hết cho $2019$.\r\n\r\nVì làm thế thì dễ quá nên bạn sẽ phải xử lý $q$ truy vấn, chúc may mắn!\r\n\r\n## Input\r\n- Dòng đầu tiên nhập số $q$ là số truy vấn.\r\n- Sau đó là $q$ dòng, mỗi dòng nhập một xâu $S$.\r\n- Dữ liệu đảm bảo tổng độ dài các xâu $S$ nhập vào không quá $5 \\cdot 10^5$.\r\n\r\n## Output \r\n- Gồm $q$ dòng, mỗi dòng in ra một số duy nhất là kết quả bài toán.\r\n\r\n## Scoring\r\n- Subtask #1 ($40\\%$ số điểm): Độ dài các xâu $S$ nhập vào không quá $18$.\r\n- Subtask #2 ($30\\%$ số điểm): Tổng độ dài các xâu $S$ nhập vào không quá $10000$.\r\n- Subtask #3 ($30\\%$ số điểm): Không có ràng buộc gì thêm.\r\n\r\n## Example\r\n\r\n**Sample input**\r\n```\r\n3\r\n1817181712114\r\n14282668646\r\n2112\r\n```\r\n\r\n**Sample output**\r\n```\r\n3\r\n2\r\n0\r\n```\r\n\r\n## Note \r\n\r\nTrong truy vấn $1$, có $3$ cặp số thỏa mãn $(1,5)$ (tạo được số $18171$), $(5,9)$ (tạo được số $18171$) và $(9,13)$ (tạo được số $12114$).\r\n\r\n*Nguồn: Atcoder*","points":1700.0,"partial":true,"time_limit":2.0,"memory_limit":1048576,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}