Xếp nến

Những ngọn nến lung linh huyền ảo khiến biết bao người đam mê, trong số đó có Nhan_Tai. Một hôm, Tai_Nhan đưa cho anh \(n\) cây nến với độ cao đôi một khác nhau. Theo đó, Nhan_Tai sẽ phải xếp \(n\) cây nến này theo một đường thẳng sao cho các cây nến ở vị trí chẵn thì cao hơn hai cây nến hai bên (nếu có), và dĩ nhiên, các cây nến ở vị trí lẻ thì thấp hơp hai cây nến hai bên (nếu có). Cụ thể, cách xếp phải thỏa mãn với mọi \(1 ≤ i ≤ n\):

• Nếu \(i\) chẵn: \(i > 1\) ⇒ \(h_{i−1} < h_{i}\); \(i < n\) ⇒ \(h_{i+1} < h_{i}\)

• Nếu \(i\) lẻ: \(i > 1\) ⇒ \(h_{i−1} > h_{i}\) ; \(i < n\) ⇒ \(h_{i+1} > h_{i}\)

Ở đây \(h_{i}\) được hiểu như là độ cao của cây nến xếp ở vị trí thứ \(i\) trên đường thẳng. Anh ta muốn biết mình có bao nhiêu cách khác nhau để xếp các cây nến. Vốn nhìn xa trông rộng, Nhan_Tai biết sẽ có thể có rất nhiều cách xếp, anh ta chỉ yêu cầu in ra \(9\) chữ số tận cùng của số cách xếp

Input

• Dòng đầu chứa \(2\) số nguyên \(Q\) là số lượng testcase

• Mỗi testcase nằm trên một dòng chứa đúng một số nguyên dương: \(n\)

Output

Gồm \(Q\) dòng trả lời cho \(Q\) testcase

Example

5
6
7
8
9
10

000000061
000000272
000001385
000007936
000050521

Scoring

• \(N, Q ≤ 5000\)

• Có \(50\%\) số test với \(n ≤ 100\)