ASM

Justas takes part in programming olympiads. Because solving tasks takes a lot of time, he wants a program that, given a task's tests, automatically finds a solution. Help him!

You are given a list of tests and must find a single program that solves all of them. Each test is a pair of numbers: an initial number and a result. The initial numbers of the tests are all distinct.

The programs are written in a very simple language with a single variable $X$ that holds a non-negative integer of arbitrary size ($X \ge 0$). When a program starts, the test's initial number is stored in $X$. A program is a list of commands:

• add n — add $n$ to $X$ ($0 \le n < 10^{18}$)
• multiply n — multiply $X$ by $n$ ($0 \le n < 10^{18}$)
• print — output the current value of $X$, written in decimal with no leading zeros (except that a value of $0$ is printed as 0). The value is printed with no separators and no newline.

For one test, the program's output is the concatenation of everything its print commands write. For example, the program

multiply 2
print
add 5
print

started with the initial number $1$ outputs 27, and started with the initial number $6$ outputs 1217.

Among all programs that produce the correct output for every test, Justas wants one with the fewest commands. Report that minimum number of commands.

The first line contains an integer $N$ — the number of tests. Each of the next $N$ lines contains two integers $a_i$ and $b_i$: $a_i$ is the initial number of the $i$-th test and $b_i$ is the output that must be produced. All $a_i$ are distinct.

Print a single integer — the minimum possible number of commands in a program that produces the correct output for every test. If no such program exists, print -1.

• $1 \le N \le 50$
• $0 \le a_i, b_i < 10^{18}$