Description

这周的数学课上，小 P 的老师讲了居民身份证号相关的一些知识。

小 P 知道，居民身份证号是由数字、大写字母 X 组成的一个字符串。其中第 $1∼6$ 位是所在地的代码，第 $7∼14$位是出生年月日，第 $17$ 位表示性别，奇数表示男性，偶数表示女性，第 $18$ 位是校验码，是通过前 $17$ 位计算得出的。其中，除了第 $18$ 位可能包含 X（用来表示数 $10$）以外，其他位都只含有数字 0-9。

小 P 非常好奇校验码的计算方法，于是他通过上网查询，得知校验码是按照如下方式计算的：

1. 把身份证前 $17$ 位分别乘以不同的系数，然后再求和。这 $17$ 个系数分别是 7,9,10,5,8,4,2,1,6,3,7,9,10,5,8,4,2。
2. 把求出来的和除以 $11$，得到一个余数。
3. 余数只可能介于 $0$ 到 $10$ 之间，分别对应最终的校验码是 1,0,X,9,8,7,6,5,4,3,2。

小 P 现在虚构了一些居民身份证号出来，你需要判断每个身份证号是否符合上面的规则（不用判断所在地代码是否真实存在，不用判断出生日期是否合法）。

如果不符合规则，输出 Invalid ID，如果符合规则，请你输出两个字符串，第一个字符串是出生日期（无需去除前导零），第二个字符串是性别，其中 Male 表示男性，Female 表示女性。

输出请注意大小写。

Input Format

第一行一个正整数 $T$，表示小 P 虚构出的居民身份证号的个数。保证 $1≤T≤1000$。

接下来 $T$ 行，每行一个字符串 $S$，表示小 P 虚构的这个居民身份证号。保证字符串 $S$ 只包含数字 0-9 和大写英文字母 X，保证 $S$ 的长度是 $18$ 并且中间不含多余空白字符。

Output Format

共 $T$ 行，每行对应一个小 P 的询问。

如果身份证号不合法，输出 Invalid ID。

如果合法，输出两个由空格分开的字符串 $s,t$，$s$ 表示出生日期（无需去除前导零），$t$ 是 Male 或 Female，分别表示男性、女性。

4
123456200001011220
123456200001011225
123XXX200001011220
12345600010000007X

20000101 Female
Invalid ID
Invalid ID
00010000 Male

Hint

样例解释

第一个询问，对各位进行加权求和之后得到的结果是 $177$，除以 $11$ 得到的余数是 $1$，对应最终校验码是 $0$。

第二个询问，校验码不合法。

第三个询问，在不是第 $18$ 位的地方出现了 X。

第四个询问，注意我们不校验日期 00010000 的合法性。

数据范围与提示

对于 $100\%$ 的数据，保证 $1≤T≤1000$，$S$ 的长度为 $18$，$S$ 只包含数字 0-9 和大写英文字母 X 并且中间不含多余空白字符。