Недавно Рудольф услышал, что в следующем году литераторы будут праздновать двухсотдвадцатипятилетие со дня рождения Александра Сергеевича Пушкина. Рудольф начал развлекаться, выбирая случайно какие-нибудь день, месяц, год и подсчитывая, сколько будет дней рождения у родившегося в данный день до определённого года.
Однако Рудольф понял, что не всё так просто, если день рождения был 29 февраля, ибо этот день есть только в високосных годах. Високосным является год, чей номер либо делится без остатка на $$$400$$$, либо делится без остатка на $$$4$$$, но не делится на $$$100$$$. Поэтому данные люди будут праздновать день рождения далеко не каждый год.
Пока Рудольф занят подготовкой к празднованию для рождения Пушкина, подсчитайте, сколько раз был день рождения человека, родившегося в заданную дату до указанного года включительно. При этом тот год, когда человек родился, учитывать не надо.
Первая строка содержит целое число $$$T$$$ ($$$1 \le T \le 10^5$$$) — количество тестов.
Следующие $$$T$$$ строк содержат описания тестов. Каждый тест содержит целые числа $$$D$$$, $$$M$$$, $$$Y$$$, $$$YE$$$ ($$$1 \le D \le 31$$$, $$$1 \le M \le 12$$$, $$$1 \le Y \lt YE \le 2 \cdot 10^6$$$) — соответственно день, месяц, год рождения и номер года, до которого нужно подсчитать количество дней рождения. Гарантируется, что дата является корректной.
Выведите $$$T$$$ целых чисел — количество дней рождения, которые будут отпразднованы в каждом из тестов.
5 15 1 1975 1976 15 1 1975 2020 7 10 2002 3001 29 2 2024 2140 29 2 2020 2035
1 45 999 28 3
