Problem:


  MathJax.Hub.Config({ tex2jax: { inlineMath: [["$","$"], ["\\(","\\)"]], processEscapes: true }});

Elevator Hall Number
-->

エレベーターホール・ナンバー

JAG (Japanese Alumni Group) は東京都某所のとある高層ビルに本部を置く謎の組織である．
このビルでは $N$ 台のエレベーターが動いており，$i$ 台目のエレベーターは $low_i$ 階から $high_i$ 階までの各階に停まる ($1 \le i \le N$)．

JAG の新スタッフである X 氏は，本部を訪れようとビルのエレベーターホールまで辿り着いた．
そこでボタンを押してエレベーターを待っていた X 氏は，エレベーターが現在いる階の表示が少々変わっていることに気づいた．
$i$ 台目のエレベーターが $a_i$ 階にいるとき，$a_1, a_2, \ldots, a_N$ をこの順に並べて，十進表記で・先頭に 0 を加えず・空白を挟まずに繋げて書いた 1 つの数がディスプレイに映されるのである．
例えば，$N = 3$ で，エレベーターが順に $10$ 階，$2$ 階，$11$ 階にいるとき，$10211$ が表示される．

X 氏は，ディスプレイに映される可能性がある数は全部で何通りあるかが気になってしまった．
あなたの課題は，それを求めるプログラムを作成することである．

Input

入力は複数のデータセットからなり，各データセットは以下の形をしている．

$N$
$low_1$ $high_1$
...
$low_N$ $high_N$

データセットの最初の行は，エレベーターの台数を表す整数 $N$ ($2 \le N \le 6$) からなる．
続く $N$ 行のうち $i$ 行目は，$2$ 個の整数 $low_i$, $high_i$ ($1 \le low_i \le high_i \le 99$) からなり，$i$ 台目のエレベーターが動く範囲を表す．

入力の終わりは，ゼロを $1$ 個だけ含む行で表される．

Output

各データセットに対して，ディスプレイに映される可能性がある数の個数を $1$ 行で出力せよ．

Sample Input

2
1 11
1 11
3
10 10
2 2
11 11
4
89 91
1 12
1 12
89 91
5
1 8
2 76
10 19
6 16
33 42
6
10 59
20 69
30 79
40 89
50 99
50 99
0

Output for Sample Input

120
1
1278
659520
15625000000



Sample input:
2
1 11
1 11
3
10 10
2 2
11 11
4
89 91
1 12
1 12
89 91
5
1 8
2 76
10 19
6 16
33 42
6
10 59
20 69
30 79
40 89
50 99
50 99
0


Sample output:
120
1
1278
659520
15625000000

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
write = sys.stdout.write
def solve():
    N = int(readline())
    if N == 0:
        return False
    A = [0]*N; B = [0]*N
    for i in range(N):
        A[i], B[i] = map(int, readline().split())
    dp = [[0]*(1 << (3*N)) for i in range(2*N+1)]
    for i in range(1, 10):
        c = 0
        if A[0] <= i <= B[0]:
            c |= 1
        if A[0]//10 <= i < B[0]//10 or A[0]//10 == B[0]//10 == i:
            c |= 2
        if A[0]//10 < i <= B[0]//10:
            c |= 4
        dp[1][c] += 1
    N0 = 1 << (3*N)
    for i in range(1, N*2):
        dp0 = dp[i]
        dp1 = dp[i+1]
        for j in range(1, N0):
            v = dp0[j]
            if v == 0:
                continue
            for k in range(10):
                c = 0
                for l in range(N):
                    a0 = A[l]; b0 = B[l]
                    s = 1 << (3*l)
                    if j & s and l < N-1 and k > 0:
                        a1 = A[l+1]; b1 = B[l+1]
                        if a1 <= k <= b1:
                            c |= (s << 3)
                        if a1//10 <= k < b1//10 or a1//10 == b1//10 == k:
                            c |= (s << 4)
                        if a1//10 < k <= b1//10:
                            c |= (s << 5)
                    if j & (s << 1):
                        if j & (s << 2):
                            c |= s
                        elif a0//10 == b0//10:
                            if a0%10 <= k <= b0%10:
                                c |= s
                        elif a0%10 <= k:
                            c |= s
                    if j & (s << 2):
                        if k <= b0%10:
                            c |= s
                if c:
                    dp1[c] += v
    ans = 0
    for i in range(2*N+1):
        dpi = dp[i]
        ans += sum(dpi[j] for j in range(N0) if j & (1 << (3*N-3)))
    write("%d\n" % ans)
    return True
while solve():
    ...