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 `Y`_{1}-`M`_{1}-`D`_{1} and `Y`_{2}-`M`_{2}-`D`_{2} (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.

The first line of the input is an integer `T` (1 ≤ `T` ≤ 10^{5}), indicating the number of test cases. Then `T` test cases follow. For each test case:

The first and only line contains six integers `Y`_{1}, `M`_{1}, `D`_{1}, `Y`_{2}, `M`_{2}, `D`_{2}, their meanings are described above.

It's guaranteed that `Y`_{1}-`M`_{1}-`D`_{1} is not larger than `Y`_{2}-`M`_{2}-`D`_{2}. Both `Y`_{1}-`M`_{1}-`D`_{1} and `Y`_{2}-`M`_{2}-`D`_{2} are 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++.

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

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

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.

提交代码