For many many years, mathematicians all over the world have focused their attention on one of the most fascinating phenomenon of Maths: the relationship between the perimeter and the diameter of a circumference (π). Using one of Euler’s formulas, we can calculate π as an addition of infinite terms, π = 1 + 1/2 + 1/3 + 1/4 − 1/5 + 1/6 + 1/7 + 1/8 + 1/9 − 1/10 + 1/11 + 1/12 − 1/13 + . . . Some of these terms add on, and others subtract, according to the following rules, • You put ‘+’ if the denominator of the fraction is 2. • You put ‘+’ if the denominator of the fraction is a prime like 4m − 1, for some integer m. • You put ‘−’ if the denominator of the fraction is a prime like 4m + 1, for some integer m. • If the denominator is not a prime number, you put the sign resultant of multiplying the signs corresponding to each prime factor. For example, the term with denominator 3 has ‘+’ because 3 is prime and 3 = 4 × 1 − 1. The term with denominator 13 has ‘−’ because 13 is prime and 13 = 4 × 3 + 1. The term with denominator 6 has ‘+’ because 6 = 2 × 3, and 2 and 3 have respectively ‘+’. And the term with denominator 10 has ‘−’because10=2×5,and2has‘+’and5has‘−’. So,50is5×5×2,i.e.,−×−×+=+. We want to obtain the sign of the i-th term of the former Euler’s formula, i.e., the sign of the term with denominator i. Input The first line of the input contains an integer, t, indicating the number of test cases. For each test case, one line appears containing an integer i, 2 ≤ i ≤ 100000. Output For each test case the output should contain a single line, indicanting the sign of the term 1/i of Euler’s formula (+ or -). Sample Input 6 2 13 45 87 88 100000
2/2 Sample Output