Problem Description

What? MMM is learning Combinatorics!?
Looks like she is playing with the bell sequence now:
bell[n] = number of ways to partition of the set {1, 2, 3, ..., n}

e.g. n = 3:
{1, 2, 3}
{1} {2 3}
{1, 2} {3}
{1, 3} {2}
{1} {2} {3}
so, bell[3] = 5

MMM wonders how to compute the bell sequence efficiently.

Input

T -- number of cases
for each case:
　　n (1 <= n < 2^31)

Output

for each case:
　　bell[n] % 95041567

6
1
2
3
4
5
6

1
2
5
15
52
203