Content:
简体中文
住在喵星上的寧寧是個十足的貓咪愛好者,為了能夠每天環繞在貓咪之中,她在家裡養了非常多的貓咪。由於貓咪的數量龐大,縱使飼料批發商已經以非常低廉的價錢賣飼料給寧寧了,貓咪飼料的開銷仍依然龐大。為了避免浪費太多錢,寧寧每隔一段時間便會統計究竟有幾隻貓咪在她家中,以控制飼料的量。
然而,隨著貓口膨脹,寧寧漸漸無法計算究竟有幾隻貓咪在她家中。為此,寧寧發明了一種新方法來計算貓咪的數量,稱之為「寧寧點貓」。寧寧點貓的方法很簡單。寧寧首先選擇 N 相異的質數 P1, P2, P3, . . . , PN 。接著寧寧會對貓咪們下 N 次指示,第 i 次時寧寧會要求貓咪們每 Pi 隻組成一團,最後落單找不到組的貓咪便來找寧寧。
如此經過 N 次的指示之後,寧寧便能知道貓咪的數量除以這些質數的餘數,並可以逆推出貓咪的數量了!當然,不論質數怎麼選,可能的貓咪數量依然會有無限種,但寧寧相信貓咪的數量一定是這所有可能中最少的那個!
發明了這個方法之後,寧寧便迫不及待的對貓咪們下了指示,但她很快的就發現了一個問題:她不知道該怎麼逆推出貓咪的數量!由於明天就要買飼料了,寧寧沒時間從頭數過,她找上傳說中數學非常好的你。究竟,你能不能幫助寧寧算出貓咪的數量呢?
Input:
輸入的第一行有一個正整數 T 代表測試資料的筆數,接下來的每一行代表一筆測試資料。
每一筆測試資料的開頭有一個正整數 N 代表寧寧選了幾個質數。接下來跟著 2N 個整數,奇數項是寧寧所選的質數 Pi,而其對應的偶數項 Ri 便是最後來找寧寧的貓咪數量。
Output:
對於每一筆測試資料,請輸出貓咪的數量到底是多少。
如果貓咪的數量大於等於 955049953 隻,請輸出 −1 來告訴寧寧該少養些貓咪了。
Sample Input:
3 2 3 1 5 4 3 5 1 7 1 11 1 10 2 0 3 2 5 4 7 5 11 1 13 1 17 1 19 1 23 1 29 1
Sample Output :
4 1 -1
Hint
:
範例說明:
第三筆測試資料中,貓咪的數量為 955049954 ,故必須輸出 −1 。
Author
: