지루한 수
면접 대비시간 제한20초메모리 제한1024 MB
왼쪽부터 홀수 자리는 홀수, 짝수 자리는 짝수인 수를 [L, R] 범위에서 세는 문제로, 자릿수 DP 방식의 접두 계산이 필요하다.
문제
Ron은 지루한 수에 관한 책을 읽었다. 책에 따르면, 양의 정수의 각 자릿수를 왼쪽에서 오른쪽으로 1부터 번호를 매길 때, 짝수 번째 자리의 숫자가 모두 짝수이고 홀수 번째 자리의 숫자가 모두 홀수이면 그 수를 지루한 수라고 한다. 예를 들어 1478은 홀수 번째 자리의 숫자가 {1, 7}로 모두 홀수이고 짝수 번째 자리의 숫자가 {4, 8}로 모두 짝수이므로 지루한 수이다.
두 수 L과 R이 주어질 때, Ron은 구간 [L, R] (L과 R 포함)에 있는 지루한 수의 개수를 세려고 한다. Ron은 이 문제를 풀 수 없어서 여러분의 도움이 필요하다.
입력
입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 한 줄에 두 수 L과 R로 이루어진다.
출력
각 테스트 케이스마다 Case #x: y 형식의 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호(1부터 시작)이고 y는 지루한 수의 개수이다.
제한
- 1 ≤ T ≤ 100.
힌트
샘플 케이스 #1에서 구간에 있는 수는 {5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15}이고 이 중 {5, 7, 9, 10, 12, 14}가 지루한 수이므로 답은 6이다.
샘플 케이스 #2에서 구간에 있는 수는 {120, 121, 122, 123, 124, 125}이고 이 중 {121, 123, 125}가 지루한 수이므로 답은 3이다.
샘플 케이스 #3에서 구간에 있는 수는 {779, 780, 781, 782, 783}이고 이 중 {781, 783}이 지루한 수이므로 답은 2이다.