E. Геометр прогресс

хугацааны хязгаарлалт 1 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

$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$)-д хуувахад гарах үлдэгдэлийг хэвлэ.

Орчуулсан: Баттулга

Жишээ тэстүүд

Оролт
2
2 2
4 1
Гаралт
4
Оролт
2
2 2
3 3
Гаралт
-1

Тэмдэглэл

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

Сэтгэгдлүүдийг ачааллаж байна...