Given a date, calculate the number of days until next Easter according to canonical (western) rule using the Gregorian Calendar.

Input

First line of input is a positive integer t<100, the number of testcases. Each of the following t lines contains a single date (1600<year<2100). The example below shows the date format.

Output

For every date print the number of days until next Easter or 0 if it's an Easter date.

Example

Input:
3
18 April 2011
27 February 1954
7 July 1777

Output:
6
50
286