题目链接：https://cn.vjudge.net/problem/ZOJ-3950 

If we represent a date in the format YYYY-MM-DD (for example, 2017-04-09), do you know how many 9s will appear in all the dates between Y1-M1-D1 and Y2-M2-D2 (both inclusive)?

Note that you should take leap years into consideration. A leap year is a year which can be divided by 400 or can be divided by 4 but can't be divided by 100.

Input

The first line of the input is an integer T (1 ≤ T ≤ 105), indicating the number of test cases. Then T test cases follow. For each test case:

The first and only line contains six integers Y1, M1, D1, Y2, M2, D2, their meanings are described above.

It's guaranteed that Y1-M1-D1 is not larger than Y2-M2-D2. Both Y1-M1-D1 and Y2-M2-D2are between 2000-01-01 and 9999-12-31, and both dates are valid.

We kindly remind you that this problem contains large I/O file, so it's recommended to use a faster I/O method. For example, you can use scanf/printf instead of cin/cout in C++.

Output

For each test case, you should output one line containing one integer, indicating the answer of this test case.

Sample Input

4
2017 04 09 2017 05 09
2100 02 01 2100 03 01
9996 02 01 9996 03 01
2000 01 01 9999 12 31

Sample Output

4
2
93
1763534

Hint

For the first test case, four 9s appear in all the dates between 2017-04-09 and 2017-05-09. They are: 2017-04-09 (one 9), 2017-04-19 (one 9), 2017-04-29 (one 9), and 2017-05-09 (one 9).

For the second test case, as year 2100 is not a leap year, only two 9s appear in all the dates between 2100-02-01 and 2100-03-01. They are: 2017-02-09 (one 9) and 2017-02-19 (one 9).

For the third test case, at least three 9s appear in each date between 9996-02-01 and 9996-03-01. Also, there are three additional nines, namely 9996-02-09 (one 9), 9996-02-19 (one 9) and 9996-02-29 (one 9). So the answer is 3 × 30 + 3 = 93.

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<string>
#include<cstring>
#include<map>
#include<vector>
#include<set>
#include<list>
#include<stack>
#include<queue>
using namespace std;
typedef long long ll;
int d[2][13]={0,31,28,31,30,31,30,31,31,30,31,30,31,
              0,31,29,31,30,31,30,31,31,30,31,30,31};
int f(int x){
	int ans=0;
	while(x){
		if(x%10==9) ans++;
		x/=10;
	}
	return ans;
} 
int sum[10005][15][35];
int judge(int x){
	if((x%4==0&&x%100!=0)||(x%400==0)) return 1;
	return 0;
}
int main(){
	int psum=0;
    for(int i=2000;i<=9999;i++){
    	int y=f(i);
    	int r=judge(i);
    	for(int j=1;j<=12;j++){
    		int m=f(j);
    		for(int k=1;k<=d[r][j];k++){
    			sum[i][j][k]=psum+y+m+f(k);
    			psum=sum[i][j][k];
			}
		}
	}
    int T;
    scanf("%d",&T);
    while(T--){
    	int y1,m1,d1,y2,m2,d2;
    	scanf("%d%d%d%d%d%d",&y1,&m1,&d1,&y2,&m2,&d2);
    	int ans=sum[y2][m2][d2]-sum[y1][m1][d1]+f(y1)+f(m1)+f(d1);
    	printf("%d\n",ans);
    	
    	
	}
	return 0;
}