Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana

Un conjunto de enteros $S$, se dice especial , si  uno de los elementos que lo forma, coincide con su cardinalidad y no contiene ningún subconjunto propio que sea especial. Algunos ejemplos de este tipo de conjuntos son [ 2 , 3], [6, 10, 11, 9, 5 ], [ 1 ], etc. Para este problema, usted debe calcular la cantidad de subconjuntos especiales que contiene el conjunto [1, 2, …, N]. Por ejemplo, si $N = 3$, existen solamente 2 subconjuntos especiales: [1] y [2, 3].

Input

Línea 1 : Un entero $T$, la cantidad de casos $(1 \le T \le 10^5)$.
Línea 2…T+1 : Un entero $N$ por línea $(1 \le N \le 10^9)$.

Output

Línea 1…T : Por cada línea, imprima la cantidad de subconjuntos especiales de [1, 2, …, N]. Como este número puede ser enorme, calcule el resultado módulo 987654321.

Sample test(s)