지루한 수

Ron은 지루한 수에 관한 책을 읽었다. 책에 따르면, 양의 정수에서 짝수 위치에 있는 모든 자릿수가 짝수이고 홀수 위치에 있는 모든 자릿수가 홀수이면 그 수를 지루한 수라고 한다. 자릿수의 위치는 왼쪽에서 오른쪽으로 1부터 센다. 예를 들어, 수 1478은 홀수 위치에 홀수인 자릿수 {1, 7}가 있고 짝수 위치에 짝수인 자릿수 {4, 8}가 있으므로 지루한 수이다.

두 수 L과 R이 주어질 때, Ron은 범위 [L, R]에서 지루한 수가 몇 개인지 세려고 한다(L과 R 포함). Ron은 이 문제를 풀 수 없으므로 여러분의 도움이 필요하다.

제한

시간 제한: 20초. 메모리 제한: 1 GB. 1 ≤ T ≤ 100.

테스트 세트 1

1 ≤ L ≤ R ≤ $10^{3}$.

테스트 세트 2

1 ≤ L ≤ R ≤ $10^{18}$.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 두 수 L과 R이 있는 한 줄로 구성된다.

각 테스트 케이스마다 Case #x: y를 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호이며(1부터 시작), y는 지루한 수의 개수이다.

예제 케이스 #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이다.