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.