Migrated from Lutece 1299 Date

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

A special day is the day that is $x^{th}$ day in that month, and happens to be $x^{th}$ day in that week.

In February $1^{st}$ in $2016$, this day in that month happens to be the first day in that week, so we call it a special day.

Now, given a time interval, how many special days in total?

Input

The first line is an integer $T(T \le 55)$, denoting the number of test cases.

Then $T$ lines follows, each test case one line.

Each line contains two dates $A$ and $B$, following such format: year month day.

$year \le 10^9$, $month$ and $day$ will be legal.

$A$ and $B$ will all be later than $2016/1/31$, and $B$ will not be earlier than $A$.

Output

For each query, output the answer in one line.

Samples

2
2016 2 1 2016 2 7
2016 2 1 2022 6 1

7
77

Note

Note that the answer may be large, please using long long

Resources

The 14th UESTC Programming Contest Preliminary