Problem Description

You are given two sets of digits $S$ and $T$, where all elements are integers between $0$ and $9$.

A “perfect number” is a number whose digits contain all digits in $S$ and contain none of the digits in $T$.

For example, if $S=\{1,3,4\}$ and $T=\{7,8\}$, then $1345$, $341166$, and $4133129$ are perfect numbers, while $13$, $8431$, and $34171$ are not (because $13$ does not contain digit $4$, and although $8431$ and $34171$ contain digits $1$, $3$, and $4$, they also contain $8$ and $7$).

Find the sum of all perfect numbers in $[l,r]$.

Input Format

The first line contains a positive integer $T$, indicating the number of test cases.

Then follow $T$ test cases:

The first line contains two positive integers $l,r$.

The second line: first input a positive integer $n_S$ representing the number of elements in $S$, followed by $n_S$ integers representing the elements of $S$.

The third line: first input a positive integer $n_T$ representing the number of elements in $T$, followed by $n_T$ integers representing the elements of $T$.

Output Format

For each test case, output one integer: the sum of all perfect numbers in $[l,r]$.

3
11 40
1 3
2 4 7
2018 20170901
1 4
1 7
19260817 998244353
3 2 5 6
4 0 7 8 9

310
52885750312822
2039707997741122

Hint

Sample Explanation

For the first sample test case, the perfect numbers are:

$13$, $23$, $30$, $31$, $32$, $33$, $35$, $36$, $38$, $39$.

So the total sum is $310$.

Constraints

For $30\%$ of the testdata, $1 \le l \le r \le 10^4$.

For another $10\%$ of the testdata, $n_S=n_T=0$.

For $100\%$ of the testdata, $1 \le T \le 2000$, $1 \le l \le r \le 10^9$, $0 \le n_S,n_T \le 10$. It is guaranteed that all elements in $S$ and $T$ are integers in $[0,9]$.

Translated by ChatGPT 5