给出一个身份证号码，判断该身份证号码是否有效。判断规则如下：

1、身份证号码只有15位和18位，没有其它位数的身份证号码。

2、对于18位的身份证号码，需要检验出生日期是否合法，同时需要校验检验码(最后一位）是否正确（其它位上的数字数字默认都符合实际要求）。

出生日期校验：取身份证号码的第7-14位，由这8位组成的日期是否是真实存在的日期。其中7-10位是出生年份，11-12位是出生月份，13-14位当月第几天。比如:370722196303074013 这个身份证号码的出生日期位:19630307  其中：1963是出生的年份，03表示3月份出生，07表示3月第7天。即1963年3月7日是这个身份证的出生日期。

校验校验码步骤如下：

身份证号码的最后一位是检验码。正确的校验码由以下步骤生成。

步骤1：将前面身份证号码17位数分别乘以不同的系数。从第1位到第17位的系数分别为7, 9, 10, 5, 8, 4, 2, 1, 6, 3, 7, 9, 10, 5, 8, 4, 2。

步骤2：将这17位数字和系数相乘的结果相加。

步骤3：用加出来和除以11;得到一个余数

步骤4：这个余数只可能是0-10之间的11个数字，这个0-10共11个数子分别对应'1', '0', 'X', '9', '8', '7', '6', '5', '4', '3', '2'这个11个字符，如果对应错误，则校验失败，否则校验成功。

举例：例如：370722196303074013这个身份证，前面17位数字乘以系数之和=3*7+7*9+0*10+7*5+2*8+2*4+1*2+9*1+6*6+3*3+0*7+3*9+0*10+7*5+4*8+0*4+1*2=295，295除以11余9，则9对应的数字应该为3，如果身份证号码的最后一位是3，说明检验成功。否则校验失败。说明：370722196303074013是有效的。而370722196303074014,因为最后一位是4不是3，则说明校验失败。

3、15位的身份证号码，没有检验位。因为15位的身份证号码都是1980年以前发放的身份证号码，而且出生日期都是在1900-1980年之间的身份证。对于15位的身份证号码，需要在第6位后边插入19，插入之后身份证号码变成17位。对于15位的身份证号码需要校验出生日期是否合法，如果合法再根据第2步中步骤1-步骤4计算出最后一位校验位。最后输出这个15位变成18位后的身份证号码。

总之一句话，对于给出的18位身份证号码，需要校验出生日期是否合法，还需要校验最后一位校验码是否合法，对于15位的身份证号码，如果出生日期合法，则需要生成对应的18位身份证号码，如果出生日期不合法，则判断为无效身份证号码。

此题为一个多组输入

第一行输入一个整数T,表示测试组数。

接下来有T行，每行输入一个身份证号码

一共有T行，每行需要根据身份证号码进行判断输出

1、如果身份证号码既不是15位也不是18位，则输出"Invalid ID number"

2、如果日期不合法，则输出"Invalid ID number";

3、如果身份证号码是18位，则只需判断检验位是否正确。如果正确则输出"valid ID number"，否则输出"Invalid ID number"

4、如果身份证号码是15位，则输出转换后的18位身份证号码。

注意：输入的身份证号码长度<=100,而且输入数据保证身份证号码的除日期和检验码之外都是正确的

，只需按照号码长度、出生日期、检验位是否正确进行判断

身份证号码只包含数字字符和'X'

数据范围

50%的数据保证输入的日期都是合法的

t<=1000

字符串