Cerința

Se dau n întrebări de forma: Câte palindromuri există în intervalul [a, b]?, unde a și b sunt numere naturale date, cu a ≤ b.

Date de intrare

Fișierul de intrare nr_pal.in conține pe prima linie numărul natural nenul n, iar pe următoarele n linii, n perechii de forma a b ce reprezintă capetele intervalelor.

Date de ieșire

Fișierul de ieșire nr_pal.out va conține răspunsurile la cele n întrebări, fiecare pe câte un rând.

Restricții și precizări

• 0 < n ≤ 100.000
• 0 ≤ a ≤ b ≤ 1.000.000.000

Exemplu

nr_pal.in

2
5 23
1 255

nr_pal.out

7
34

Explicație

La prima întrebare în intervalul [5,23] exista 7 palindromuri: 5,6,7,8,9,11,22.

#include <bits/stdc++.h>
using namespace std;
ifstream cin("nr_pal.in");
ofstream cout("nr_pal.out");

int nrcif(int n)
{
    int cnt = 0;
    if(n <= 9)
        return 1;
    while(n)
    {
        cnt++;
        n /= 10;
    }
    return cnt;
}

int put(int n)
{
    int p = 1;
    for(int i = 1 ; i <= n ; i++) p *= 10;
    return p;
}

int f(int n)
{
    int ogl = n;
    while(n)
    {
        ogl = ogl * 10 + n % 10;
        n /= 10;
    }
    return ogl;
}

int ff(int n)
{
    int ogl = n;
    n /= 10;
    while(n)
    {
        ogl = ogl * 10 + n % 10;
        n /= 10;
    }
    return ogl;
}

int pal(int n)
{
    int cnt = 0;
    int nr = nrcif(n);
    for(int i = 1 ; i < nr ; ++i)
        cnt = cnt+ put((i - 1) / 2) * 9;
    int p = put((nr - 1)/2);
    int y = n/put((nr / 2));
    cnt = cnt + (y - p + 1);
    if(nr % 2 == 0)
    {
        if(f(y) > n) cnt--;
    }
    else if(ff(y) > n) cnt--;
    return cnt;
}

int main()
{
    int n;
    int a , b;
    cin >> n;
    for(int i = 0 ; i < n ; ++i)
    {
        cin >> a >> b;
        cout << pal(b) - pal(a - 1) << '\n';
    }
    return 0;
}