Cerința

Greacă este patronul firmei Grexy300, care produce periferice și componente. Fiind Black Friday, acesta vine pe piața cu niște produse noi și extrem de avansate, dar încă nu a găsit denumirile potrivite. Din propria experiența, știe că numele de produse care sunt cuvinte palindromice, nu prea atrag clienții. Așa că se întreabă, câte cuvinte de lungime x nu sunt palindromice. El are n lungimi de care este interesat. Tu fiind noul prieten și angajat al lui Greacă, trebuie să îi răspunzi la întrebări modulo 666013. Desigur că nu faci toate aceste eforturi degeaba, vei primi 100 de puncte și un salariu pe măsură.

Date de intrare

Pe prima linie a fișierului de intrare grexy.in se va afla numărul n, iar pe următoarele n linii se vor afla n numere x[i], reprezentând lungimile de care este interesat Greacă.

Date de ieșire

Pe fiecare din cele n linii ale fișierului de ieșire grexy.out se va afla câte un număr reprezentând câte cuvinte de lungime x[i] nu sunt palindromice modulo 666013.

Restricții și precizări

• 1 ≤ n ≤ 500.000
• Lungimile vor fi numere naturale nenule mai mici ca 100.000
• Un cuvânt conține doar litere mici ale alfabetului englez

Exemplu:

grexy.in

3
1
2
3

grexy.out

0
650
16900

Explicație

Toate cuvintele de o literă sunt palindromuri. Pentru cele de lungime 2 : prima cifra poate fi oricare (26 de posibilități), iar cea de a doua poate fi oricare în afară de prima (25 posibilități), deci în total 26•25 = 650. Pentru cuvintele de lungime 3, trebuie să mă credeți pe cuvânt.