Project Euler #19: Counting Sundays

_{This problem is a programming version of Problem 19 from projecteuler.net}

You are given the following information, but you may prefer to do some research for yourself.

1 Jan 1900 was a Monday.
Thirty days has September,
April, June and November.
All the rest have thirty-one,
Saving February alone,
Which has twenty-eight, rain or shine.
And on leap years, twenty-nine.

A leap year occurs on any year evenly divisible by , but not on a century unless it is divisible by .

How many Sundays fell on the first of the month between two dates(both inclusive)?

Input Format

The first line contains an integer , i.e., number of test cases.
Each testcase will contain two lines
on first line denoting starting date.
on second line denoting ending date.

Constraints

Output Format

Print the values corresponding to each test case.

Sample Input

Sample Output

18
35

Explanation

For testcase 1, we have the following sundays :-

1 April 1900
1 July 1900
1 September 1901
1 December 1901
1 June 1902
1 February 1903
1 March 1903
1 November 1903
1 May 1904
1 January 1905
1 October 1905
1 April 1906
1 July 1906
1 September 1907 
1 December 1907
1 March 1908
1 November 1908
1 August 1909