Bạn được cho một xâu \(S\) gồm các chữ số từ \(1\) đến \(9\).

Nhiệ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\).

Vì làm thế thì dễ quá nên bạn sẽ phải xử lý \(q\) truy vấn, chúc may mắn!

Input

• Dòng đầu tiên nhập số \(q\) là số truy vấn.
• Sau đó là \(q\) dòng, mỗi dòng nhập một xâu \(S\).
• 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\).

Output

• 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.

Scoring

• Subtask #1 (\(40\%\) số điểm): Độ dài các xâu \(S\) nhập vào không quá \(18\).
• Subtask #2 (\(30\%\) số điểm): Tổng độ dài các xâu \(S\) nhập vào không quá \(10000\).
• Subtask #3 (\(30\%\) số điểm): Không có ràng buộc gì thêm.

Example

Sample input

3
1817181712114
14282668646
2112

Sample output

3
2
0

Note

Trong 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\)).

Nguồn: Atcoder