住在喵星上的寧寧是個十足的貓咪愛好者，為了能夠每天環繞在貓咪之中，她在家裡養了非常多的貓咪。由於貓咪的數量龐大，縱使飼料批發商已經以非常低廉的價錢賣飼料給寧寧了，貓咪飼料的開銷仍依然龐大。為了避免浪費太多錢，寧寧每隔一段時間便會統計究竟有幾隻貓咪在她家中，以控制飼料的量。

然而，隨著貓口膨脹，寧寧漸漸無法計算究竟有幾隻貓咪在她家中。為此，寧寧發明了一種新方法來計算貓咪的數量，稱之為「寧寧點貓」。寧寧點貓的方法很簡單。寧寧首先選擇 N 相異的質數 P₁, P₂, P₃, . . . , P_N 。接著寧寧會對貓咪們下 N 次指示，第 i 次時寧寧會要求貓咪們每 Pi 隻組成一團，最後落單找不到組的貓咪便來找寧寧。

如此經過 N 次的指示之後，寧寧便能知道貓咪的數量除以這些質數的餘數，並可以逆推出貓咪的數量了！當然，不論質數怎麼選，可能的貓咪數量依然會有無限種，但寧寧相信貓咪的數量一定是這所有可能中最少的那個！

發明了這個方法之後，寧寧便迫不及待的對貓咪們下了指示，但她很快的就發現了一個問題：她不知道該怎麼逆推出貓咪的數量！由於明天就要買飼料了，寧寧沒時間從頭數過，她找上傳說中數學非常好的你。究竟，你能不能幫助寧寧算出貓咪的數量呢？ 

輸入的第一行有一個正整數 T 代表測試資料的筆數，接下來的每一行代表一筆測試資料。

每一筆測試資料的開頭有一個正整數 N 代表寧寧選了幾個質數。接下來跟著 2N 個整數，奇數項是寧寧所選的質數 P_i，而其對應的偶數項 R_i 便是最後來找寧寧的貓咪數量。

• T ≤ 1000
• N ≤ 1000
• 2 ≤ P_i ≤ 1000
• 0 ≤ R_i < P_i

對於每一筆測試資料，請輸出貓咪的數量到底是多少。

如果貓咪的數量大於等於 955049953 隻，請輸出 −1 來告訴寧寧該少養些貓咪了。

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

4
1
-1

範例說明： 

第三筆測試資料中，貓咪的數量為 955049954 ，故必須輸出 −1 。