This page is still under construction.

Parts of this page are still being built. What you see may change.

Calendar Game

Time limit1sMemory limit128 MB

Summary
On a fixed 1900-2001 calendar, two players alternately advance a date by one day or to the same day next month; decide if the first player wins.
Level

Medium6 of 10

Topics
Game theory, Dynamic programming, Implementation
Solved
No attempts yet

Problem

Sangbeom and Mingyun are once again competing in the World Couples Programming Contest. On the night before the contest, the two stayed up all night playing a calendar game to celebrate.

The calendar game is played on a calendar that spans the dates from January 1, 1900 to November 4, 2001, and it starts from an arbitrary date within this range. Sangbeom moves first, and then the two alternate turns in the order Sangbeom → Mingyun → Sangbeom → Mingyun → …. On each turn, the current player chooses one of the following two moves:

  1. Move to the day immediately after the current date.
  2. Move to the date in the next month that has the same day-of-month as the current date. This move is allowed only if such a day actually exists in the next month.

For example, if the current date is December 19, 1924, the player may move to either December 20, 1924 or January 19, 1925. However, if the current date is January 31, 2001, February has no 31st, so the only possible move is to February 1, 2001.

The player who first reaches November 4, 2001 wins. If a move would carry the date past November 4, 2001, the player who made that move loses.

Given the starting date, write a program that determines whether the first player, Sangbeom, has a guaranteed winning strategy.

This calendar also has leap years. A year is a leap year if it is divisible by 4, except that years divisible by 100 are not leap years, unless they are also divisible by 400. In a leap year February has 29 days; otherwise it has 28 days.

Input

The first line contains the number of test cases TT. Each of the following TT lines contains one starting date in the format YYYY MM DD, where YYYY is the year, MM is the month, and DD is the day. For example, 2001 11 04 means November 4, 2001. Every starting date is a valid date between January 1, 1900 and November 4, 2001, inclusive.

Output

For each test case, print YES on its own line if Sangbeom has a guaranteed winning strategy, or NO otherwise.

Examples2

  1. Example 1

    Input
    3
2001 11 3
2001 11 2
2001 10 3
    Expected output
    YES
NO
NO

  2. Example 2

    Input
    1
1900 01 01
    Expected output
    YES