测试数据来自 nnu_contest/1233

C.约数(Hard)

时间限制：2秒
空间限制：64MB

题目背景

本题的Easy版本和Hard版本的唯一区别是：

Hard版本中\(T\le 10^5 \) 且\(N\leq 10^{18}\)

有时候，相对于题目描述，样例更能帮助你快速理解题意。

题目描述

銅メダルを目指して、高橋さんと青木さんはICPCコンテストに参加しています。

コンテストの初めに、彼らは問題Aの問題文を読みます。

問題Aは非常に簡単なようです。問題文は

「正整数 N が与えられます。 N の正の奇数の約数と正の偶数の約数はどちらが多いか答えてください。T個のテストケースが与えられるので、それぞれについて答えを求めてください。」

ただし、正整数 N は非常に大きくなる場合があるので、彼らは有効な対策が思いつきません。

答えを出力してください。

输入格式

第一行包含一个正整数T，表示数据组数。

第2~T+1行每行包含一个正整数N。

输出格式

请输出T行，每行表示该测试数据对应的答案。

如果正整数N的正约数中奇数更多，请输出Odd

如果正整数N的正约数中偶数更多，请输出Even

如果正整数N的正约数中奇数和偶数一样多，请输出Same

数据范围及限制

\(1\le T \le 10^5\)

\(1\le N \le 10^{18}\)

样例输入

3
2
998244353
1000000000

样例输出

Same
Odd
Even

样例解释

2只有1和2两个约数，所以奇数约数和偶数约数同样多。
998244353只有1和998244353两个约数，所以奇数约数较多。