정수 정규식 (Large)

문제

이 문제에서 올바른 정규식은 다음 중 하나이다. 아래 설명에서 E1, E2 등은 올바른 정규식을 나타내며, 서로 같아도 된다.

십진 숫자 하나: 0 1 2 3 4 5 6 7 8 9 중 하나이다.
연결: E1E2.
선택: (E1|E2|...|EN). 식은 두 개 이상이어야 하며, 바깥 괄호는 반드시 있어야 한다.
반복: (E1)*. 바깥 괄호는 반드시 있어야 한다.

예를 들어 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 = E1E2이고, D = D1D2이면서 각 Ei가 Di와 매치되는 D1, D2가 존재한다.
E = (E1|E2|...|EN)이고, Ei 중 하나 이상이 D와 매치된다.
E = (E1)*이고, 어떤 음이 아닌 정수 N에 대해 D = D1D2...DN이면서 E1이 모든 Di와 매치되는 D1, D2, ..., DN이 존재한다. 특히 (E1)*는 빈 문자열과도 매치된다.

예를 들어 정규식 ((1|2))*3은 3, 13, 123, 2221123 등과 매치된다. 반면 1234, 3123, 12, 33 등과는 매치되지 않는다.

올바른 정규식 R이 주어질 때, A 이상 B 이하의 정수 중 앞에 0이 붙지 않은 십진 표기가 R과 매치되는 정수는 몇 개인가?

입력

첫째 줄에 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어지며, 각 테스트 케이스는 두 줄로 이루어진다. 첫째 줄에는 구하려는 정수 범위의 양 끝(양 끝 포함)인 양의 정수 A와 B가 주어진다. 둘째 줄에는 0123456789()|*에 속한 문자로만 이루어진 문자열 R이 주어진다. R은 위에서 설명한 올바른 정규식임이 보장된다.

제한

$1 \le T \le 100$
$1 \le A \le B \le 10^{18}$
$1 \le$ (R의 길이) $\le 30$

출력

각 테스트 케이스마다 Case #x: y 형식으로 한 줄을 출력한다. x는 1부터 시작하는 테스트 케이스 번호이고, y는 구간 [A, B]에 속한 정수 중 정규식 R과 매치되는 정수의 개수이다.

힌트

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