有一个云服务 API 用于帮助用户存储历史时间戳。每个用户的数据结构最初是一个空栈。每当你向 API 发送一个包含整数 $x$（表示当前时间戳）的请求时，服务会将 $x$ 追加到栈的末尾。当 $x$ 小于栈中存储的上一个时间戳时，服务会认为输入有误，并追加上一个时间戳而不是 $x$。

你总共向 API 发送了 $n$ 次请求，第 $i$ 次调用的请求时间戳为 $x_i$。然而，网络出现了故障。服务可能会以任意顺序接收你的请求，甚至可能丢失部分请求。已知此问题，你请求值班工程师查看数据库中你的栈。假设服务恰好接收到了 $k$ 个请求，那么可能存在多少种不同的栈？

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 100$)，表示测试用例的数量。对于每个测试用例：

第一行包含一个整数 $n$ ($1 \le n \le 3000$)，表示请求的总数。

第二行包含 $n$ 个整数 $x_1, x_2, \dots, x_n$ ($1 \le x_i \le 10^9$)，表示每次请求的时间戳。

保证所有 $n$ 的总和不超过 $30\,000$。

输出格式

对于每个测试用例，输出 $n$ 行，第 $i$ 行 ($1 \le i \le n$) 包含一个整数，表示当 $k = i$ 时不同栈的数量。注意答案可能非常大，请输出其对 $10^9 + 7$ 取模的结果。

样例

样例输入 1

2
3
1 2 3
3
2 3 3

样例输出 1

3
5
5
2
2
2

说明

在第一个样例中：

• 当 $k = 1$ 时，栈可以是 $[1], [2]$ 或 $[3]$。
• 当 $k = 2$ 时，栈可以是 $[1, 2], [1, 3], [2, 2], [2, 3]$ 或 $[3, 3]$。
• 当 $k = 3$ 时，栈可以是 $[1, 2, 3], [1, 3, 3], [2, 2, 3], [2, 3, 3]$ 或 $[3, 3, 3]$。

在第二个样例中：

• 当 $k = 1$ 时，栈可以是 $[2]$ 或 $[3]$。
• 当 $k = 2$ 时，栈可以是 $[2, 3]$ 或 $[3, 3]$。
• 当 $k = 3$ 时，栈可以是 $[2, 3, 3]$ 或 $[3, 3, 3]$。