题目描述

某实验基地有一排按编号排列的 $n$ 块太阳能板，构成首尾不相连的队列。现要从中选取若干块太阳能板，按照原有编号次序排列后，这些太阳能板的高度构成一个非降序列(即序列中任何一个数都不小于它之前的任何一个数)。

请编写程序，选出最多的太阳能板使得高度构成非降序列，并求出满足条件的选取方案总数。

输入格式

第一行一个正整数 $m$，表示有 $m$ 组数据。

每组数据的格式为 $n, h_1, h_2, h_3, \ldots, h_n$，其中 $h_i$ 表示第 $i$ 块太阳能板的高度。

输出格式

对每组数据输出一行，包含两个整数 $t$ 和 $c$，分别表示最长非降子序列的长度和方案数。

样例

3
9 10 1 9 8 7 6 3 4 6
3 100 70 102
6 40 37 23 89 91 12

4 1
2 2
3 3

提示

$m \leq 5$，$n \leq 20$，$h_i \leq 150$。