$a, ab, ab^{2}, ab^{3}, ...$ геометр прогрессын эхний элемент нь $a$ ба ялгавар нь $b$

Танд $n$ ширхэг геометр прогресс өгөгдсөн ба таны даалгавар бол хамгийн бага бүх геометр прогрессын гишүүн болдог $x$ тоог олох эсвэл байдаггүйг тодорхойлох явдал юм.

Оролт

Эхний мөрөнд өгөгдөх геометр прогрессуудын тоо ($1 ≤ n ≤ 100$)

Дараагийн $n$ мөрөнд геометр прогрессуудын эхний гишүүн ба ялгавар $a, b$ ($1 ≤ a, b ≤ 10^{9}$) тус бүр нэг нэг мөрөнд өгөгдөнө.

Гаралт

Хэрвээ бүх прогрессын гишүүн болох тоо олдохгүй бол $ -1$ гэж хэвлэнэ. Эсрэг тохиолдолд бүх прогрессын гишүүн болдог тоог $1000000007$ ($10^{9} + 7$)-д хуувахад гарах үлдэгдэлийг хэвлэ.

Хоёрдох жишээн дээр прогрессуудын нэг нь дан хоёрын зэргүүдээс тогтоно харин нөгөө нэг нь дан гурвын зэргүүдээс тогтоно.