정수 정규 표현식

이 문제에서 유효한 정규 표현식은 다음 중 하나이다. 아래 설명에서 $E_{1}$, $E_{2}$ 등은 서로 다를 필요가 없는 유효한 정규 표현식을 나타낸다.

• 십진 숫자: 즉, 0 1 2 3 4 5 6 7 8 9 중 하나이다.

• 이어 붙이기: $E_{1}$ $E_{2}$.

• 선택: 두 개 이상의 표현식에 대해 ($E_{1}$|$E_{2}$ |...|$E_{N}$)이다. 바깥쪽 괄호가 필수임에 유의한다.

• 반복: ($E_{1}$)*. 바깥쪽 괄호가 필수임에 유의한다.

예를 들어, 7, 23, (7)*, (45)*, (1|2|3), ((2)*|3), (1|2|3), ((0|1))*은 유효한 표현식이다. (7), 4|5, 4*, (1|), (0|1)*은 유효하지 않다.

다음 중 적어도 하나가 참일 때, 그리고 그럴 때에만 표현식 E가 숫자 문자열 D와 일치한다고 한다.

• E = D.

• E = $E_{1}$ $E_{2}$이고, D = $D_{1}$ $D_{2}$이면서 $E_{i}$이 $D_{i}$과 일치하도록 하는 $D_{1}$와 $D_{2}$가 존재한다.

• E = ($E_{1}$| $E_{2}$|...| $E_{N}$)이고, $E_{i}$ 중 적어도 하나가 D와 일치한다.

• E = ($E_{1}$)*이고, 어떤 음이 아닌 정수 N에 대해 D = $D_{1}$ $D_{2}$...$D_{N}$이면서 $E_{1}$이 각각의 $D_{i}$와 일치하도록 하는 $D_{1}$, $D_{2}$, ..., $D_{N}$가 존재한다. 특히 ($E_{1}$)*은 빈 문자열과 일치함에 유의한다.

예를 들어, 표현식 ((1|2))*3은 여러 문자열 중 3, 13, 123, 2221123와 일치한다. 하지만 여러 문자열 중 1234, 3123, 12, 33과는 일치하지 않는다.

유효한 정규 표현식 R이 주어질 때, A 이상 B 이하인 정수 중 R이 그 정수의 선행 영이 없는 10진법 표현과 일치하는 것은 몇 개인가?

제한

시간 제한: 테스트 세트당 20초. 메모리 제한: 1 GB. 1 ≤ T ≤ 100. 1 ≤ A ≤ B ≤ $10^{18}$. 1 ≤ R의 길이 ≤ 30.

작은 데이터 세트 (테스트 세트 1 - 공개)

R에는 | 문자가 포함되지 않는다.

큰 데이터 세트 (테스트 세트 2 - 비공개)

추가 제한은 없다.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어지며, 각 테스트 케이스는 두 줄로 이루어진다. 첫 줄에는 관심 있는 정수 범위의 양 끝을 포함하는 경계를 나타내는 두 양의 정수 A와 B가 주어진다. 둘째 줄에는 집합 0123456789()|*의 문자로만 이루어진 문자열 R이 주어지며, R은 위의 문제 설명에서 정의한 유효한 정규 표현식임이 보장된다.

각 테스트 케이스마다 Case #x: y을 포함하는 한 줄을 출력한다. 여기서 x은 1부터 시작하는 테스트 케이스 번호이고, y은 양 끝을 포함하는 범위 [A, B]에서 정규 표현식 R과 일치하는 정수의 개수이다.

예제 케이스 5부터 8까지는 작은 데이터 세트에 등장하지 않음에 유의한다.

예제 케이스 1에서 범위 내에서 일치하는 것은 1, 10, 100, 1000이다.

예제 케이스 2에서 범위 내에서 일치하는 것은 379009이다.

예제 케이스 3에서 범위 내에서 일치하는 것은 12, 34, 1212, 1234, 3434이다.

예제 케이스 4에서는 범위 내에서 일치하는 것이 없다.

예제 케이스 5에서 범위 내에서 일치하는 것은 1, 10, 11, 100이다.

예제 케이스 6에서 범위 내에서 일치하는 것은 23과 45이다.

예제 케이스 7에서는 범위 내의 어떤 수도 만들 수 있다.

예제 케이스 8에서 범위 내에서 일치하는 것은 1, 19, 156, 179, 189, 199이다.