404512: GYM101522 D Distribution of Days

The Gregorian calendar is internationally the most widely used civil calendar. It is named after Pope Gregory XIII, who introduced it in October 1582.

In the Gregorian calendar, there are 28 days in February in a common year and 29 days in February in a leap year. Year Y is a leap year if and only if Y is a multiple of 400, or Y is a multiple of 4 and is not a multiple of 100.

Percy is curious about the distribution of days of the week of his birthday in his life. By checking the calendar, he quickly finds that in the years between 1999 and 2017 (inclusive), his birthday (in case you do not know, 27 February) appears only twice on both Tuesday and Thursday, three times on each of the other days of the week.

Percy finds counting the distribution of some days in some consecutive years really cool, so he decides to invent a way to quickly count the distribution.

Within 15 minutes, he successfully invented a fast program to do the calculation for years between 1583 and 2 × 10⁹, inclusive. His program can answer 5000 queries in 1 second. However, he is not sure if the program works correctly, so he needs your help. Your task is simple, write your own program to do the calculation, so that Percy can check his program's correctness by comparing the outputs of different queries with your program.

In this problem, please assume the definition of leap years mentioned above is true for all years between 1583 and 2 × 10⁹, inclusive.

The first line consists of a single integer, Q, denotes the number of queries. (1 ≤ Q ≤ 5000)

In the next Q lines, each describes a single query. The queries are in the format S E M D, which means you have to calculate the distribution of days of the week for the D-th day of the M-th month for all years between S and E, inclusive. (1583 ≤ S ≤ E ≤ 2 × 10⁹, the days given are one of the 366 valid days)

Output Q lines, each answers a query given.

In each line output 7 integers, the frequencies of days of the weeks in this order: Sunday, Monday, Tuesday, Wednesday, Thursday, Friday, Saturday.

The order of answers should follow the order of queries given.

1
1999 2017 2 27

3 3 2 3 2 3 3

2
2017 2017 8 15
2017 2021 2 29

0 0 1 0 0 0 0
0 0 0 0 0 0 1

4
3141 5926 5 3
5897 9323 8 4
2718 2818 2 8
2222 2222 2 22

404 391 403 390 404 396 398
488 488 497 481 497 480 496
15 14 14 15 14 15 14
0 0 0 0 0 1 0