Elevator Hall Number

Elevator hall number

JAG (Japanese Alumni Group) is a mysterious organization headquartered in a skyscraper somewhere in Tokyo. There are $N$ elevators in operation in this building, and the $i$ elevators stop on each floor from the $low_i$ floor to the $high_i$ floor ($1 \ le i \ le N$).

Mr. X, a new staff member of JAG, arrived at the elevator hall of the building to visit the headquarters. Mr. X, who pressed a button and waited for the elevator, noticed that the display on the floor where the elevator is currently located has changed slightly. When the $i$ elevator is on the $a_i$ floor, arrange $a_1, a_2, \ ldots, a_N$ in this order, and connect them in decimal notation with no leading 0 and no spaces. The one number you write is shown on the display. For example, if $N = 3$ and the elevators are on the $10$ floor, the $2$ floor, and the $11$ floor in that order, $10211$ will be displayed.

Mr. X was wondering how many numbers could be shown on the display. Your task is to create a program that seeks it.

Input

The input consists of multiple datasets, each of which has the form:

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

The first row of the dataset consists of the integer $N$ ($2 \ le N \ le 6$) representing the number of elevators. Of the following $N$ lines, the $i$ line consists of $2$ integers $low_i$, $high_i$ ($1 \ le low_i \ le high_i \ le 99$), and the $i$ elevator is Represents the range of movement.

The end of the input is represented by a line containing only $1$ of zeros.

Output

For each dataset, print the number of possible displays in $1$ lines.

Sample Input

2 1 11 1 11 3 10 10 twenty two 11 11 Four 89 91 1 12 1 12 89 91 Five 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

Example

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

120 1 1278 659520 15625000000

inputFormat

Input

The input consists of multiple datasets, each of which has the form:

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

The first row of the dataset consists of the integer $N$ ($2 \ le N \ le 6$) representing the number of elevators. Of the following $N$ lines, the $i$ line consists of $2$ integers $low_i$, $high_i$ ($1 \ le low_i \ le high_i \ le 99$), and the $i$ elevator is Represents the range of movement.

The end of the input is represented by a line containing only $1$ of zeros.

outputFormat

Output

For each dataset, print the number of possible displays in $1$ lines.

Sample Input

2 1 11 1 11 3 10 10 twenty two 11 11 Four 89 91 1 12 1 12 89 91 Five 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

Example

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

120 1 1278 659520 15625000000

样例

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

120
1
1278
659520
15625000000

</p>