Integer Roots of a Polynomial

Time Limit: 1 Second    Memory Limit: 32768 KB

A polynomial of degree n has the common form as

p(x) = a[n]*x^n + a[n-1]*x^(n-1) + ... + a[1]*x + a[0].

In general it is difficult to find the roots of a polynomial of degree 3 or higher, unless you have a powerful computer program available. The following observation might be helpful:

Let p(x) be a polynomial with integer coefficients. If p(c) = 0 for some integer c, then (x - c) is a factor of p(x) and c is a divisor of the constant term of p(x).

Your task is to write a program to find all the integer roots of a given polynomial with integer coefficients.

Input

The first line of input contains a positive integer N (N <= 100), then followed by N test cases. Each test case consists of 2 lines of integers: the first line contains a non-negative integer n (n <= 20) which is the degree of the polynomial; and the second line contains n+1 integers a[n], a[n-1], ..., a[1], and a[0]. Note that 0-polynomial will not appear in the input.

Output

For each test case, print in one line all the integer roots of the given polynomial in ascending order. The roots must be separated by one space. If there is no integer root at all, just print "NIR" (means No Integer Root).

Sample Input

3
3
-1 18 -96 160
2
1 0 1
2
2 3 0

Sample Output

4 4 10
NIR
0

Submit

Source: Zhejiang University Local Contest 2003