11264 - Coin Collector

Sultan到某個國家旅行，該國流通的硬幣共有 n 種，他想要儘可能的收集最多種不同的硬幣。假設他想從該國銀行提領X元，而銀行會以下列演算法兌換硬幣給他：

withdraw(x) {
    if(X == 0) return;
    令Y為其值不超過X且面額最大的硬幣。
    給客戶一個Y元的硬幣。
    withdraw(X-Y);
}


Sultan可以從銀行提領任意數量的金錢，他想要在一次的提領之中領取最多種不同的硬幣。

Input:

輸入資料的第一列有一個整數T表示測試資料的組數，每組測試資料以一個整數 n (1 <= n <= 1000)表示不同面額的硬幣數，下一列有 n 個整數C1, C2, ..., Cn分別表示硬幣的面額，且C1 < C2 < C3 < ... < Cn < 1000000000。C1必為1。

Output:

請對每組測試資料輸出Sultan一次最多可以從銀行拿到幾種不同的硬幣。

Sample Input	Sample Output
2 6 1 2 4 8 16 32 6 1 3 6 8 15 20	6 4

---

原文出處