問題文

整数 $N$ が与えられます。素数 $p$ と非負整数 $r$ であって、二項係数 ${}_pC_r$ が $N$ と等しくなるものは存在しますか？

入力

$k$
$p_1$ $e_1$
$\vdots$
$p_k$ $e_k$

• $N$ は素因数分解した形で与えられ、$N=\prod_{i=1}^{k}p_i^{e_i}$ である
• $k\geq 1$
• $2\leq p_1 < \ldots < p_k \leq 10^7$
• $1\leq e_i\leq 10^7$

出力

$N={}_pC_r$ を満たす $10^{49}$ 以下の素数 $p$ と非負整数 $r$ が存在するとき、$p,r$ の順に空白区切りで出力し改行せよ。解が複数ある場合、どれを出力しても正解となる。
そのような $p,r$ が存在しないなら、かわりに -1 -1 と出力し改行せよ。
末尾に余計な出力があっても正解となる。

サンプル

2
2 1
5 1

5 2

2
2 2
5 1

-1 -1