11743 - Credit Check

今日，用信用卡網路購物已經變得相當普遍，由於使用者可能打錯信用卡號，所以一般電子商務型網站都會對信用卡號作檢查。
其中一種錯誤檢查機制稱為Luhn algorithm，它可以把所有打錯一個位數的錯誤找出來，甚至於能挑出打錯多個位數的錯誤，它的檢查規則如下：
用一個例子來講解會比較方便，例如信用卡號(5181 2710 9900 0012)：

1. 將偶數位置上的數字乘2，也就是將(5181 2710 9900 0012)中粗體底線的數字乘2，得到10, 16, 4, 2, 18, 0, 0, 2。
2. 將剛剛所得到的數字中每一個位數數值加總，即(1+0) + (1+6) + 4 + 2 + (1+8) + 0 + 0 + 2 = 25。將信用卡號中奇數位數的數字作加總，即1+1+7+0+9+0+0+2 = 20，再將兩數相加25+20=45。
   
3. 45的個位數並非0，所以這個信用卡號並不合法。

本題請你用此法檢查信用卡號是否正確。

Input Format
輸入的第一列為整數N，表示測試資料的組數，接下來的N列分別為一個信用卡號，信用卡號有16個數目字，四個數字一組以一個空白字元隔開。

Output Format 
若信用卡號是檢查合格的，請輸出"Valid"，否則請輸出"Invalid"。

Sample Input

2

5181 2710 9900 0012

5181 2710 9900 0017

Sample Output

Invalid

Valid

---

原文出處