중국인 ID는 아래와 같이 구성되어 있다.

1. 총 18글자로 구성되어 있다.
2. 처음 17글자는 모두 숫자이고, 이를 Body Code 라고 부른다.
3. 마지막 1글자는 숫자 또는 'X' 이며 Checksum Code 라고 부른다.
4. Body Code 는 3 부분으로 구성된다. 
   1. 지역코드: 6자리 숫자이며, 다음 중 하나인 경우에만 유효하다. "000001", "000010", "000100", "001000", "010000", "100000"
   2. 생일코드: 8개의 숫자. YYYYMMDD 형식. 19000101 ~ 20141231 범위만 유효하다. (윤년 조심)
   3. 순서코드: 3자리 숫자이며, 000 은 유효하지 않다. 홀수이면 남자, 짝수이면 여자를 의미한다.
5. Checksum 은 Body Code 를 앞에서부터 a1, a2, ..., a17 이라고 하면 checksum = (a1 * 2^17 + a2 * 2^16 + ... + a17 * 2^1) % 11 이다. checksum 의 범위는 0 ~ 10 이며 10의 경우'X'로 표기한다.

중국인 ID가 문자열로 주어졌을 때 유효성을 판단하여,유효하지 않으면 "Invalid" 를 반환하고, 유효하면 성별("Male" or "Female")을 출력하라.

첫 줄에는 테스트 케이스의 수 T ( 1 <= T <= 200) 이 주어지며 2번째 줄부터 T+1 번째 줄까지는 중국인의 아이디 18글자가 주어집니다.

각 줄에 하나씩 판단 결과를 출력 해 주세요.