Black Star hates people that are not symmetrical. He defines symmetry for numbers as either horizontal symmetry (each digit, when cut in half horizontally, must have the same upper half as lower half), or vertical symmetry (when cutting the number at the middle digit/digits, the ~i^\text{th}~ digit from the half towards the start must be equal to the ~i^\text{th}~ digit from the half towards the end). Each city in his country is indexed from ~1~ to ~N~, and for a city ~x~ its citizens are numbered from ~10^{x-1}~ to ~10^x - 1~ (all the natural numbers of ~x~ digits). Furthermore, we know that Black Star will visit ~Q~ cities out of the ~N~, and for each of them he wants to know how many people in that city he hates. However, since the number is pretty large, he asks us the number ~\bmod 666\,013~. Since we also have other tasks at hand given by Black Star, we ask you to give us the answer for the ~Q~ cities.

Constraints

Subtask 1 [50%]

~1 \le Q \le N \le 3\,000~

Subtask 2 [50%]

~1 \le Q \le N \le 1\,000\,000~

Input Specification

On the first line, there will be two space separated integers ~N~ and ~Q~.
On the second line, there will be the ~Q~ cities Black Star asks about.

Output Specification

There will be ~Q~ numbers, each number on a separate line.
The number on the ~i^\text{th}~ line will be the answer to the ~i^\text{th}~ city from the input.

Sample Input

3 2
1 2

Sample Output

0
77