Dog vs Cat

题号：NC265538
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

小蓝最近在异世界的国度中生活，最近国度中丞相的空缺，有两位候选人，我们称其中一人为 Dog 先生，另一人为 Cat 先生，他们俩因为谁上位的问题一直摩擦不断，国王也很无奈，于是请小蓝解决这个问题，小蓝想到了一个办法：给定长度为 $\mathit n$ 的序列 $\mathit a$ ， Dog 先生和 Cat 先生每次可以将序列 $\mathit a$ 中的某个非零数减一，两人轮流操作， Cat 先生先手，若某人无法进行操作或者操作后出现以下局面则输掉比赛：

1、设 $\mathit x$ 为序列 $\mathit a$ 中的最小数，设 $cnt[x]$ 为数字 $\mathit x$ 在序列 $\mathit a$ 中出现的次数， $n-cnt[x] \leq cnt[x] <n$ 。

2、 $\mathit x=\text 0$ 且 $cnt[x]= \mathit n$ 。

国王看到这个游戏觉得很好，于是下令谁赢得这场游戏谁就是新的丞相，已知 Dog 先生和 Cat 先生都发挥最佳，最终是谁成为了新丞相？

输入描述:

第一行包含一个整数 ，表示测试用例的组数。
对于每组测试用例：
第一行输入一个正整数  。
第二行输入  个整数表示序列  。
保证  。

输出描述:

对于每组测试用例：

输出一个字符串，若Cat先生成为新丞相输出 "Cat" ，否则输出 "Dog" (不带引号)。

示例1

输入

复制

1
4
1 2 3 4

输出

复制

Cat