軟體金鑰，又叫 CD Key ，是軟體開發商用來驗證使用者是否有乖乖花錢買正版軟體的一種方式。使用者透過合法管道購買軟體時，包裝內會附上一份由數個字元所組成的軟體金鑰，使用者在第一次使用軟體時，需將金鑰輸入軟體進行驗證，軟體開發商會利用一套特殊的算法用來驗證金鑰是否有效。驗證金鑰是否有效的算法通常非常複雜（畢竟如果太簡單被人們發現規律的話，就不會有人花錢去買金鑰了...）。

你，一位天才高中生，有天無聊心血來潮，想在電腦上安裝 \(Windows \ 95\)，在驗證金鑰時，你隨手打了一串111-1111111，沒想到......什麼！！驗證竟然通過了！？

感到震驚的你，又接著嘗試了000-1111111沒想到又通過系統的驗證！天呀！真是太不可思議了，你發現 \(Windows \ 95\) 的金鑰驗證機制，前 \(3\) 碼必須是 \(000, 111\) 或 \(222\)。

在研究完前 \(3\) 碼的驗證機制後，你開始研究後 7 碼的規則，你嘗試了111-0000095、111-0000000、111-0000007、111-0000016...！不會吧！你發現除了111-0000095之外，其他組的序號竟然也都通過了，相信你已經猜到了，沒錯，後 \(7\) 碼的金鑰規則就是每位數加起來的總合必須是 \(7\) 的倍數，且同時不可以出現數字 \(9\)。

後來你還發現，金鑰有沒有打-其實不會影響最終結果（也就是說111-1111111和1111111111是等價的）。

現在，你手邊有一些長度為 \(10\) 字元的金鑰，你打算用程式模擬金鑰驗證的過程，為了方便處理，輸入的序號已自動把-省略，請你撰寫一支程式判斷金鑰是否有效。

輸入說明

第一行輸入一個整數 \(T\)，表示接下來有 \(T\) 筆測資。

每筆測資第一行給定軟體金鑰 \(K\)

• \(1 \leq T \leq 5000\)
• 保證每筆輸入的金鑰 \(K\) 長度為 \(10\) 字元

輸出說明

對於每筆測資，若金鑰 \(K\) 為有效的 \(Windows \ 95\) 金鑰，請輸出Valid，否則請輸出QAQ Invalid。

範例輸入 1

4
1111111111
0001111111
1110000007
0123456789

範例輸出 1

Valid
Valid
Valid
QAQ Invalid

範例輸入 2

3
5554862861
5555847726
2222788435

範例輸出 2

QAQ Invalid
QAQ Invalid
QAQ Invalid

子題