God

Time limit1sMemory limit1024 MB

Summary
Given the vote ratios in each of the three candidates' own polls, decide whether some consistent assignment of actual vote counts lets Donghyun collect a strict plurality. Print GOD if he can, KDH otherwise.
Level

Medium6 of 10

Topics
Number theory, Math, Implementation, Brute force
Solved
No attempts yet

Problem

Donghyun, Hyunsoo, and Seungwon have spent a long time building their skills to earn the title of god of problem solving. By now all three are skilled enough to be called a god, but there cannot be three gods under one sky. Debating how to pick the single true god, the three decided to make the person whose name fits best when the word god is attached to it the true god.

But fitting is subjective, so many opinions are needed. The three therefore gathered their own friends and held votes. Since having oneself as a candidate would make the vote unfair, each person was excluded from the candidates in their own vote. After the vote, each person takes the votes they received in the votes held by the other two, and the person with the most votes collected this way becomes the true god. If several people tie for the most votes, the vote is void. All three have many friends, so each vote is guaranteed to have at least one participant.

alt text

Example of a vote

Today the vote results are made public. But to keep each other in check, the three did not reveal the full results; they revealed only the ratio of votes the two candidates received in each vote they held! Given only the revealed results, determine whether Donghyun can become the true god.

Input

The first line gives an integer T (1 ≤ T ≤ 100,000), the number of votes held.

The next T lines each give six integers DH, DS, HD, HS, SD, SH (1 ≤ DH, DS, HD, HS, SD, SH ≤ 1,000) separated by spaces, representing the result of a vote.

  • DH, DS are the ratio of votes that god Hyunsoo and god Seungwon received in the vote Donghyun held. The two numbers are guaranteed to be coprime.
  • HD, HS are the ratio of votes that god Donghyun and god Seungwon received in the vote Hyunsoo held. The two numbers are guaranteed to be coprime.
  • SD, SH are the ratio of votes that god Donghyun and god Hyunsoo received in the vote Seungwon held. The two numbers are guaranteed to be coprime.

Output

For each of the T lines, print GOD if Donghyun can become the true god in that vote, and KDH if he cannot.

Hint

In the third example, Donghyun can become the true god if the following results come out.

alt text

Examples1

  1. Example 1

    Input
    3
3 2 3 2 2 1
2 3 1 2 1 3
1 1 2 3 1 2
    Expected output
    GOD
KDH
GOD