Số X

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Tác giả:
Small
Dạng bài
Điểm: 1500 (p) Thời gian: 1.0s Bộ nhớ: 1023M Input: bàn phím Output: màn hình

Thấy Khoa rất thích học toán, một hôm thầy giáo đã ra một bài toán cho Khoa giải như sau:

Xác định hai hàm \(f,g\) trên các số nguyên dương như sau:

  • \(f(n)\) = tích các chữ số khác 0 của \(n\)
  • \(g(n)\) có trị trị là:
    • \(n\) nếu n<10
    • \(g(f(n))\) ngược lại
      Khoa cần xử lý \(Q\) truy vấn, trong mỗi truy vấn sẽ được cung cấp 3 số nguyên \(l,r,k\). Khoa cần in số lượng số nguyên \(x\) nằm giữa \(l\) và \(r\), trong đó \(g(x)=k\).

Input

  • Dòng đầu tiên chứa số nguyên \(Q\) \((1 \le Q \le 2 \times 10^5)\) đại diện cho số lượng truy vấn
  • \(Q\) dòng tiếp theo, mỗi dòng chứa 3 số nguyên \(l,r,k (1 \le l \le r \le 10^6,1 \le k \le9)\)

Output

  • Với mỗi truy vấn, in ra một dòng chứa câu trả lời cho truy vấn đó.

Example

Test 1

Input 
4
22 73 9
45 64 6
47 55 7
2 62 4
Output 
1
4
0
8
Note
  • Có 1 số \(x\) để \(g(x)\)=9 đó là \(g(33)\)=9 với \(g(33)\)=\(g(3\times3)\)=\(g(9)\)=9
  • Có 4 số \(x\) để \(g(x)\)=6 là: \(g(47)\)=\(g(48)\)=\(g(60)\)=\(g(61)\)=6
  • Không có số \(x\) nào trong khoảng 47 đến 55 để \(g(x)\)=7.
  • Có 8 số \(x\) để \(g(x)\)=4 là: \(g(4)\)=\(g(14)\)=\(g(22)\)=\(g(27)\)=\(g(39)\)=\(g(40)\)=\(g(41)\)=\(g(58)\)=4

Bình luận


  • -8
    rukashii    9:34 p.m. 30 Tháng 12, 2021

    Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.


    • -8
      nguyendanghau2006    8:00 p.m. 31 Tháng 12, 2021

      Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.

      1 bình luận nữa