Их монгол улсын үед эзэн Чингис хаан нэгэн аян дайнд явах цэргийг бүрдүүлэн хошууч жанжинаар Зэвийг томилж түүнд нийт цэргээс дайнд орох цэргийг бүрдүүлэхдээ дараах хуулиар сонгохыг зарлигджээ. Эхлээд Цэргүүдээ нэг эгнээнд жагсааж дугаарлаад тэднээс аль ч хоёр зэрэгцэж зогссон цэргүүд ороогүй байхаар дайнд орох цэргүүдийг сонгох хэрэгтэй гэжээ. Гэхдээ Чингис хаан зарлигтаа Зэв жанжинд нэг цэрэг аваад ч дайнд орж болохыг анхааруулжээ. Тэгвэл та энэ хуулиар сонгоход гарах ялгаатай сонголтуудын нийт тоог тогтоох програм зохионо уу!

Input

Оролт хэд хэдэн тохиолдолуудтай бөгөөд эхний мөрөнд тохиолдлын тоо T(1<=T<=20) байрлана. Дараачийн мөрүүдэд тохиолдолууд буюу цэргүүдийн тоонууд нэг нэг мөрөнд байрлана. Цэргийн тоонууд xi нь (2 < xi < 10^9) байна.

Output

Гаралт нь нэг нэг мөрөнд байрлах бөгөөд тэдгээр нь оролтын тохиолдлуудад харгалзах сонголтуудын нийт тоонууд болно.Гэхдээ тэдгээрийг тус тус 10^6-д хуваагаад үлдэгдэлүүдийг хэвлэх хэрэгтэй.

Example

Input:
4
3
5
30
40


Output:
4
12
178308
914295