Another LIS

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 65536/32768 K (Java/Others)

Description

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.

Input

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.

Output

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.

Sample Input

1 3 0 0 2

Sample Output

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

Hint

zhouzeyong

Source

2010 ACM-ICPC Multi-University Training Con

提交代码