Bài tập

Một số nguyên không âm \(x\) được gọi là đẹp nếu \(x\) chia hết cho ít nhất một trong ba số \(4\), \(7\), hoặc \(11\). Nhiệm vụ của bạn là đếm số lượng các số đẹp nằm trong một khoảng \([L; R]\) cho trước.

Input

• Dòng đầu tiên chứa một số nguyên \(t\) (\(1 \le t \le 1000\)), là số lượng câu hỏi.
• \(t\) dòng tiếp theo, mỗi dòng chứa hai số nguyên dương \(L, R\) (\(0 \le L < R \le 10^{18}\)).

Output

• Với mỗi câu hỏi, in ra một số nguyên duy nhất là số lượng số đẹp trong khoảng \([L; R]\).

Example

2
1 10
11 15

3
3

Cho ba số nguyên dương \(a, b, c\) và một giới hạn \(n\). Hãy đếm số lượng số nguyên dương không lớn hơn \(n\) sao cho số đó chia hết cho một trong ba số \(a, b, c\).

Input

Gồm một dòng duy nhất chứa bốn số nguyên lần lượt là \(n, a, b\) và \(c\) \((1 \le a, b, c \le n \le 10^{12})\).

Output

Gồm một số duy nhất là số lượng số thỏa mãn yêu cầu.

Example

10 2 5 7

7

Ami rất thích sưu tập các con số đặc biệt. Theo cậu, một số càng "đơn giản" thì càng đẹp. Vì vậy, Ami chỉ quan tâm đến những số được tạo thành từ không quá \(K\) chữ số khác nhau.

Ví dụ:

• \(12222111\) chỉ sử dụng hai chữ số là \(1\) và \(2\), nên đẹp với \(K \ge 2\).
• \(505050\) chỉ sử dụng hai chữ số là \(0\) và \(5\).
• \(123456\) sử dụng sáu chữ số khác nhau.

Ami muốn tính tổng tất cả các số đẹp nằm trong đoạn \([L,R]\).

Yêu cầu. Cho ba số nguyên \(L\), \(R\) và \(K\). Hãy tính tổng các số trong đoạn \([L,R]\) mà sử dụng không quá \(K\) chữ số khác nhau.

Vì kết quả có thể rất lớn, chỉ cần in ra kết quả theo modulo \(998244353\).

\InputFile

Gồm một dòng chứa ba số nguyên

thỏa mãn

\OutputFile

In ra một số nguyên là tổng các số thỏa mãn điều kiện, lấy modulo \(998244353\).

\Examples

\beginexample
\exmp
10 50 2

1230

\exmp
1 2345 10

2750685

\exmp
101 154 2

2189

\endexample

\Note

Trong ví dụ thứ nhất, mọi số trong đoạn đều sử dụng không quá \(2\) chữ số khác nhau, nên đáp án chính là tổng các số từ \(10\) đến \(50\).

\endproblem

Bạn An đang chuẩn bị đi chơi tuy nhiên bạn sợ việc sử dụng tiền tài khoản đôi khi bị nghẽn mạng sẽ không chuyển được tiền đi xe, tiền mua các nhu yếu phẩm, mua quà, ... nên bạn nhờ cửa hàng B đổi cho mình \(n\) nghìn đồng tiền tài khoản thành tiền mặt. Để tiện cầm tiền mặt, bạn An nhờ cửa hàng B đổi tiền cho mình sao cho số tờ là nhỏ nhất có thể. Em hãy giúp cửa hàng B thực hiện công việc trên, biến rằng tiền Việt Nam có các mệnh giá : 1 nghìn đồng, 2 nghìn đồng, 5 nghìn đồng, 10 nghìn đồng, 20 nghìn đồng, 50 nghìn đồng, 100 nghìn đồng, 200 nghìn đồng, 500 nghìn đồng.

Input

Đọc từ tệp DT.INP gồm một số nguyên dương duy nhất \(n\) (\(n \le 10^9\)).

Output

Ghi vào tệp DT.OUT ghi theo cấu trúc sau :

Các dòng đầu trên mỗi dòng kê mệnh giá và số tờ tiền mặt : mệnh giá trước, số tờ sau (đặt cách nhau một dấu cách trống, các mệnh giá không có tờ nào thì không kê).

Dòng cuối cùng ghi tổng số tờ.

Example

1234

500 2
200 1
20 1
10 1
2 2
7