There is a sequence firstly empty. We begin to add number from 1 to N to the sequence, and every time we just add a single number to the sequence at a specific position. Now, we want to know length of the LIS (Longest Increasing Subsequence) after every time's add.

An integer T (T <= 10), indicating there are T test cases. For every test case, an integer N (1 <= N <= 100000) comes first, then there are N numbers, the k-th number Xk means that we add number k at position Xk (0 <= Xk <= k-1).See hint for more details.

For the k-th test case, first output "Case #k:" in a separate line, then followed N lines indicating the answer. Output a blank line after every test case.

In the sample, we add three numbers to the sequence, and form three sequences. a. 1 b. 2 1 c. 2 1 3

2010 ACM-ICPC Multi-University Training Contest（13）——Host by UESTC