Long before Gutenberg invented letterpress printing, books have been transcribed by monks. Cloisters wanted to be able to check that a book was transcribed by them (and not by a different cloister). Although watermarked paper would have been an option, the cloister preferred to use a system of hard-to-fake serial numbers for identifying their transcriptions. Each serial number consists of 10 single numbers a1, a2, . . . , a10. Valid serial numbers satisfy a1 + a2 +...+a9 ≡ a10 (modN) with 0 ≤ a10 < N. The N is specific to and only known by the cloister that has transcribed this book and is therefore able to check its origin. You are confronted with a pile of books that presumably have been transcribed by a single cloister. You are asked to write a computer program to determine that cloister, i.e. to calculate the biggest possible N that makes the serial numbers of these books valid. Obviously, no cloister has chosen N = 1. So if your calculations yield N = 1, there must be something wrong. Input Input starts with an integer t on a single line, the number of test cases (1 ≤ t ≤ 100). Each test case starts with an integer c on a single line, the number of serial numbers you have to consider (2 ≤ c ≤ 1000). Each of the following c lines holds 10 integer numbers a1,a2,...,a10 (0 ≤ ai < 228) separated by single spaces. Output For each test case, output a single line containing the largest possible N, so that each given serial number for that test case is valid. If you cannot find a N > 1 satisfying the condition for all serial numbers or if the numbers are valid independent of the choice of N, output ‘impossible’ (without the quotes) on a single line. Sample Input 4 2 1111111119 2 4 6 8 10 12 14 16 18 90 3 1111111111 5472642132 1234567895 2 1111111111 1111111110 2 2222222220 1111111111 Sample Output impossible 8
2/2 impossible 2