ASM

Justas는 프로그래밍 올림피아드에 자주 참가한다. 문제를 푸는 데 시간이 오래 걸리기 때문에, 그는 문제의 테스트를 입력하면 해답을 자동으로 찾아 주는 프로그램을 원한다. 그를 도와주자!

테스트 목록이 주어지면, 그 모든 테스트를 올바르게 처리하는 하나의 프로그램을 찾아야 한다. 각 테스트는 두 수, 즉 초기 수와 결과로 이루어진다. 각 테스트의 초기 수는 서로 다르다.

프로그램은 매우 단순한 언어로 작성된다. 이 언어에는 변수 $X$ 하나만 있으며, $X$는 크기에 제한이 없는 음이 아닌 정수를 담는다 ($X \ge 0$). 프로그램이 시작되면 테스트의 초기 수가 $X$에 저장된다. 프로그램은 다음 명령들의 목록이다.

• add n — $X$에 $n$을 더한다 ($0 \le n < 10^{18}$)
• multiply n — $X$에 $n$을 곱한다 ($0 \le n < 10^{18}$)
• print — $X$의 현재 값을 출력한다. 앞에 $0$을 붙이지 않은 십진수로 출력하며(단, 값이 $0$이면 0을 출력한다), 구분자나 줄바꿈 없이 출력한다.

한 테스트에 대한 프로그램의 출력은 모든 print 명령이 출력한 내용을 이어 붙인 것이다. 예를 들어 다음 프로그램은

multiply 2
print
add 5
print

초기 수가 $1$이면 27을, 초기 수가 $6$이면 1217을 출력한다.

모든 테스트에 대해 올바른 출력을 내는 프로그램들 중에서, Justas는 명령의 개수가 가장 적은 것을 원한다. 그 최소 명령 개수를 구하여라.

첫째 줄에 테스트의 개수 $N$이 주어진다. 다음 $N$개의 줄에는 각각 두 정수 $a_i$와 $b_i$가 주어진다. $a_i$는 $i$번째 테스트의 초기 수이고, $b_i$는 만들어 내야 하는 출력이다. 모든 $a_i$는 서로 다르다.

모든 테스트에 대해 올바른 출력을 내는 프로그램의 최소 명령 개수를 정수 하나로 출력한다. 그러한 프로그램이 존재하지 않으면 -1을 출력한다.

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