
ZOJ Problem Set  3950
If we represent a date in the format YYYYMMDD (for example, 20170409), 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. InputThe 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 20000101 and 99991231, 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++. OutputFor each test case, you should output one line containing one integer, indicating the answer of this test case. Sample Input4 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 Output4 2 93 1763534 HintFor the first test case, four 9s appear in all the dates between 20170409 and 20170509. They are: 20170409 (one 9), 20170419 (one 9), 20170429 (one 9), and 20170509 (one 9). For the second test case, as year 2100 is not a leap year, only two 9s appear in all the dates between 21000201 and 21000301. They are: 20170209 (one 9) and 20170219 (one 9). For the third test case, at least three 9s appear in each date between 99960201 and 99960301. Also, there are three additional nines, namely 99960209 (one 9), 99960219 (one 9) and 99960229 (one 9). So the answer is 3 × 30 + 3 = 93. Author: WENG, Caizhi Source: The 17th Zhejiang University Programming Contest Sponsored by TuSimple 