Let F(n) be nth fibonacci number. F(0) = 0, F(1) = 1, F(2) = 1, F(3) = 2, F(4) = 3 and so on. Given a positive integer n > 2, print the smallest prime number P such that P divides F(n) but it does not divide any F(k) smaller than F(n). Maximum value of n is limited by P where P < 2^64. You should print IMPOSSIBLE if no such P exists.

Input

First line of input contains a single positive integer T denoting number of test cases. T <= 20. Next T lines contains value of n.

Output

Output value of P corresponding to each n in separate lines.

Example

Input:
2
3
8

Output:
2
7

PS : Source Code Limit changed to 700B.