数圈圈

题目描述
tabris有一个习惯，无聊的时候就会数圈圈，无论数字还是字母。
现在tabris更无聊啦，晚上睡不着觉就开始数羊，从a只数到b只。
顺便还数了a到b之间有多少个圈。

但是tabris笨啊，虽然数羊不会数错，但很可能数错圈的个数。
但是tabris很难接受自己笨这个事实，所以想问问你他一共应该数出多少个圈，这样tabris才好判断他到底笨不笨啊。

输入描述:
输入一个T，表示数据组数
每组测试数据包含两个正整数a，b。
T∈[1,50]
a,b∈[1, ]

输出描述:
每组数据输出结果，并换行。

示例1

输入
11
1 1
2 2
3 3
4 4
5 5
6 6
7 7
8 8
9 9
10 10
1 100

输出
0
0
0
1
0
1
0
2
1
1
111

备注:
数字的圈的个数请根据样例自行理解。

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld

问题分析: 前缀和模板题，数字的圈的个数为数字中闭合环的个数，可以打表实现。由于有多组数据，为了避免重复计算，推荐将1 ~ 的圈圈数和前缀和的数组提前初始化，每组数据只需代入前缀和公式计算即可，具体代码如下。

#include <iostream>
#include <cstring>

using namespace std;

const int N = 1e6;

int c[10] = {1, 0, 0, 0, 1, 0, 1, 0, 2, 1};   // 将0 ~ 9的圈圈数打表列出
int x[N + 1], s[N + 1];

void init(){
    for(int i = 1; i <= N; i ++){   // 初始化圈圈数组
        int t = i;
        while(t){
            x[i] += c[t % 10];
            t /= 10;
        }
    }
    for(int i = 1; i <= N; i ++) s[i] = s[i - 1] + x[i];   // 初始化前缀和数组
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);

    int t, a, b;
    init();   // 初始化放在t次循环之外，避免重复计算
    cin >> t;
    while(t --){
        cin >> a >> b;
        cout << s[b] - s[a - 1] << endl;
    }
    return 0;
}