刀工对决

题号：NC217128
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

为了争夺传说中的厨具永灵刀，特级厨师小当家和七星刀雷恩展开了神前刀工对决。对决总共有 $n$ 轮刀工测试，每轮给出两块鲷鱼肉，一块长度为 $a$ ，另一块长度为 $b$ ，厨师必须把这两份鲷鱼肉切成一样长。

已知小当家总共有两把菜刀，每把作用如下：

钢丝菜刀：若当前鲷鱼肉长度 $x$ 为 $3$ 的倍数，可以切掉三分之二的鲷鱼肉，切掉的部分必须扔掉，即 $x$ 变为 $\frac{x}{3}$ 。

百穴菜刀：若当前鲷鱼肉长度 $x$ 为 $5$ 的倍数，可以切掉五分之二的鲷鱼肉，切掉的部分必须扔掉，即 $x$ 变为 $\frac{3}{5}x$ 。

小当家每使用菜刀切一刀鲷鱼肉就要花费 $1$ 秒，请问小当家完成 $n$ 轮测试的最短时间是多少。

第一行一个正整数 $n$ ， $n\leq10^{5}$ 。

接下来 $n$ 行，每行两个正整数 $a$ 与 $b$ ，其中 $a\leq10^{9}$ , $b\leq10^{9}$ 。

输出小当家完成 $n$ 轮测试的最短时间，若小当家无法完成某一轮测试，输出 $-1$ 。

示例1

复制

2
3 1
1 9

复制

第一轮测试对a使用1次钢丝菜刀，第二轮测试对b使用2次钢丝菜刀。

示例2

复制

2
5 3
1 3

复制

第一轮测试对a使用1次百穴菜刀，第二轮测试对b使用1次钢丝菜刀。

示例3

复制

2
2 3
1 1

复制

-1

第一轮测试无法将这两块鲷鱼肉长度切成一样。