Let ~tab[y]~ denote the number of occurrences of the number ~y~ in the table. We can (not in an efficient way) calculate it using the following algorithm for each ~y~ from ~1~ to ~N~:

for x from 1 to N:
    tab[x] = tab[x] + 1
    tab[x + rev(x)] = tab[x + rev(x)] + tab[x]

This algorithm is linear, but ~N~ can be up to ~10^{10}~ so it is not efficient enough. It is crucial to notice that the amount of numbers for which ~tab[y] > 1~ is very small. Let's denote the number of different numbers ~x~ such that ~x+rev(x) = y~ as ~cnt[y]~. Notice that ~cnt[y] > 0~ if and only if ~tab[y] > 1~. Let's denote the array of numbers consisting of all the numbers for which ~cnt[y] > 0~ as ~S~ and sort it ascendingly. The values of ~tab[y]~ for these numbers can be calculated using the following algorithm:

for each x in S:
    tab[x] = tab[x] + cnt[x]
    tab[x + rev(x)] = tab[x + rev(x)] + tab[x]

This algorithm consists of ~|S|~ loop iterations. It is crucial to notice that the amount of numbers in set ~S~ is relatively small (only a couple of millions) so the upper algorithm is efficient enough in order to calculate the values ~tab[y]~ for each ~y~ for which the value is larger than ~1~. For each other ~y~ it holds ~tab[y] = 1~, so now we actually have the value ~tab[y]~ calculated for each ~y~, which enables us to efficiently answer queries (using partial sums of the array tab). Notice that the indices in the array ~tab~ are very big, but we don't need the whole array so we will actually store it in a map.

We are left to calculate the values of ~cnt[y]~ for all numbers. We will recursively find all numbers ~y~ and the values ~cnt[y]~ for each ~y~ for which the value is larger than ~0~. Let's see what happens when we add a ~6~-digit number with itself, only in reverse:

    a1     a2     a3     a4     a5     a6
 +  a6     a5     a4     a3     a2     a1
-----------------------------------------
c0  b1+c1  b2+c2  b3+c3  b3+c4  b2+c5  b1

Here ~c_0, \dots, c_5~ are ~0~ or ~1~ and denote the carrying digits, ~b_1 = (a_1+a_6) \bmod 10~, ~b_2 = (a_2+a_5) \bmod 10~ and ~b_3 = (a_3+a_4) \bmod 10~.

The values ~cnt[y]~ could be determined so that we fix the digits ~a_1, \dots, a_6~ in all possible ways, but there are a lot of combinations for that. Another approach would be to determine ~b_1, b_2, b_3~ and ~c_0, \dots, c_5~ in all possible ways (therefore the sum is uniquely determined) and calculate how many different selections of ~a_1, \dots, a_6~ results in exactly ~b_1, b_2, b_3~ and ~c_0, \dots, c_5~. How can we do this? We will use a recursive function gen which takes 4 parameters, their meanings described in the following list:

• pos means we are currently determining ~b_{pos}~
• c1 means that ~c_{pos-1}~ is equal to ~c_1~
• c2 means that ~c_{6-pos+1}~ is equal to ~c_2~
• num is the value of the current part of the sum ~a_1 \dots a_6 + a_6 \dots a_1~

Here is the pseudocode for function gen:

gen(pos, c1, c2, num):

  if pos = 4:
    (we have determined the whole sum and the number of ways to obtain it)
    if c1 != c2 return
    (c1 and c2 must be equal because they both represent c3)
    increase cnt[num] by 1 and return

  for pairs of digits (x1, x2):
    (x1 and x2 determine b_pos, we are determining digits pos and 6-pos+1 of num)
    if c1 = 1 and x1+x2 < 10 continue
    if c1 = 0 and x1+x2 >= 10 continue
    bb = (x1 + x2) % 10

    nnum = num
    set digit 6-pos+1 of nnum to bb + c2
    set digit pos of nnum to bb + 1 and call
      gen(pos+1, 1, x1+x2 >= 10, nnum)
      (c1 = 1 denotes that we want the carry digit)

    set digit pos of nnum to bb and call
      gen(pos+1, 0, x1+x2 >= 10, nnum)
      (c1 = 0 denotes that there is no carry)

The upper approach can be generalized for an arbitrary number of digits. The upper recursion for a number of length ~L~ performs approximately ~81^{L/2}~ operations, which is too slow for all points. It is crucial to note that we don't need to iterate over all pairs of digits, because it is sufficient to iterate over all possible sums and for each sum know how many ways there is to obtain it. Then we perform approximately ~19^{L/2}~ operations, which is fast enough for all points. We leave the details as an exercise to the reader.