Bài 2: Số 3 (TS10 Hưng Yên 2026)

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
Ngôn ngữ cho phép
Assembly, Awk, C, C#, C++, Clang, Cobol, D, Groovy, Haskell, JS, Java, Kotlin, Lua, Node JS, OCaml, ObjectiveC, Output, PHP, Pascal, Perl, Prolog, Pypy, Pypy 3, Python, Ruby, Rust, Scala, Scratch, Swift
Điểm: 1100 (p) Thời gian: 2.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Tam rất thích các số nguyên dương chia hết cho \(3\) hoặc có tận cùng bằng \(3\). Vinh là bạn thân của Tam, Vinh thích tính toán và đã đưa ra \(q\) câu hỏi. Với câu hỏi thứ \(i\) là hai số nguyên \(L_i, R_i\) (\(1 \le i \le q, 1 \le L_i \le R_i \le 10^6\)). Vinh muốn biết có bao nhiêu số mà Tam thích trong đoạn \([L_i, R_i]\).

Input

  • Dòng đầu tiên chứa số nguyên dương \(q\).
  • \(q\) dòng tiếp theo, dòng thứ \(i\) (\(1 \le i \le q\)) chứa hai số nguyên dương \(L_i, R_i\) tương ứng câu hỏi thứ \(i\) mà Vinh đưa ra cho Tam.

Output

  • Ghi ra \(q\) dòng, dòng thứ \(i\) là số lượng số mà Tam thích trong đoạn \([L_i, R_i]\).

Constraints

  • \(1 \le L_i \le R_i \le 10^6\)
  • Subtask \(1\) (\(20\%\) số điểm): \(q = 1\).
  • Subtask \(2\) (\(20\%\) số điểm): \(1 < q \le 10\).
  • Subtask \(3\) (\(60\%\) số điểm): \(10 < q \le 10^5\).

Example

Test 1

Input 
1
4 15
Output 
5
Note

Trong ví dụ 1, có \(q = 1\) câu hỏi với đoạn \([4, 15]\), các số thỏa mãn là \(6, 9, 12, 13, 15\).

Test 2

Input 
3
2 12
8 14
16 17
Output 
4
3
0
Note

Các số Tam thích là \(3, 6, 9, 12, 13, 15, 18, 21, 23, 24, 27, 30, 33, 36, \dots\)

  • Đoạn \([2, 12]\) có \(4\) số thỏa mãn là \(3, 6, 9, 12\).
  • Đoạn \([8, 14]\) có \(3\) số thỏa mãn là \(9, 12, 13\).
  • Đoạn \([16, 17]\) không tồn tại số nào thỏa mãn.

Bình luận (1)

Mới nhất
Tải bình luận...

Kỳ thi: