Liczenie po chińsku ...okiem programisty

17.08.2009 - Agata Murawska
TrudnośćTrudność

Gra Jasia

Limit czasowy: 1000 milisekund
Limit pamięciowy: 16000 kilobajtów


Mama z Jasiem gra w grę, w której mama podaje najpierw reszty z dzielenia ilości cukierków przez pewne liczby parami względnie pierwsze. Następnie mówi Jasiowi nową liczbę,  względnie pierwszą ze wszystkimi podanymi wcześniej. Zadaniem Jasia jest podać resztę z dzielenia ilości cukierków przez tę liczbę. Mama chce dać ich mu jak najmniej - wybierze zatem najmniejszą liczbę cukierków, dającą odpowiednie reszty z dzielenia.
Jaś zastanawia się, jaką liczbę powinien podawać mamie, żeby dostać jak najwięcej cukierków. 

Wejście
W pierwszej linii znajduje się liczba testów T ( T<=1000 ). Dalej następuje T zestawów testowych opisanych poniżej.
W pierwszej linii znajduje się n - ilość par podawanych przez mamę. W kolejnych n liniach znajdują się pary ai, mi, gdzie ai  jest resztą z dzielenia liczby cukierków przez mi. Ostatnia linia zawiera liczbę p, resztę z dzielenia przez nią ma podać Jaś. Iloczyn wszystkich liczb przez które dzieli mama nie przekracza 109.

 

Wyjście
Twój program powinien wypisać T linii. W i-tej linii powinna znajdować
się jedna liczba - odpowiedź Jasia dla i-tego zestawu testowego.

Przykład

Dla wejścia
1
2
2 3
4 5
8
Prawidłowym rozwiązaniem jest
2

Nie możesz wysyłać i oglądać rozwiązań tego zadania ponieważ nie jesteś zalogowany. Zaloguj się lub załóż konto.
3.5
Twoja ocena: Brak Ocena: 3.5 (2 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com