Một bài tập thú vị về chữ số

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Xem hướng dẫn
Tác giả:
flo
Dạng bài
Ngôn ngữ cho phép
C++, Clang, Clang++, Cobol, D, Groovy, Haskell, JS, Lua, Node JS, ObjectiveC, Pascal, Prolog, Pypy 3, Python, Scala
Điểm: 1700 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Cho \(3\) số nguyên dương \(l, r, k\), hãy tính \(F(l) + F(l+1) + ... + F(r)\) với \(F(n)\) là số lần xuất hiện của chữ số \(k\) trong \(n\).

Input, Output and Scoring

Input

  • Số nguyên dương \(t\) \((1 \le t \le 10^5)\).
  • \(t\) dòng tiếp theo, mỗi dòng chứa \(3\) số nguyên dương \(l, r, k\) \((1 \le l \le r \le 10^{18}; 0 \le k \le 9)\).

Output

  • Với mỗi dòng, hãy in ra kết quả sau khi chia lấy dư cho \(1234567891\).

Scoring

  • Subtask \(1\) \((50\%)\): \(1 \le l \le r \le 10^6\).
  • Subtask \(2\) \((50\%)\): Không giới hạn gì thêm.

Example

Input

2
22 36 2
100 110 0

Output

10
12

Bình luận