A. Password

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Monocarp has forgotten the password to his mobile phone. The password consists of 44 digits from 00 to 99 (note that it can start with the digit 00).

Monocarp remembers that his password had exactly two different digits, and each of these digits appeared exactly two times in the password. Monocarp also remembers some digits which were definitely not used in the password.

You have to calculate the number of different sequences of 44 digits that could be the password for Monocarp's mobile phone (i. e. these sequences should meet all constraints on Monocarp's password).

Input

The first line contains a single integer t� (1≤t≤2001≤�≤200) — the number of testcases.

The first line of each testcase contains a single integer n� (1≤n≤81≤�≤8) — the number of digits for which Monocarp remembers that they were not used in the password.

The second line contains n� different integers a1,a2,…an�1,�2,…�� (0≤ai≤90≤��≤9) representing the digits that were not used in the password. Note that the digits a1,a2,…,an�1,�2,…,�� are given in ascending order.

Output

For each testcase, print one integer — the number of different 44-digit sequences that meet the constraints.

Example

input

Copy

2

8

0 1 2 4 5 6 8 9

1

8

output

Copy

6
216

Note

In the first example, all possible passwords are: "3377", "3737", "3773", "7337", "7373", "7733".

解题说明：水题，只需要判断已经去除了几个数，然后排列组合剩下的数字即可。

#include <stdio.h>
int main() 
{
	int t;
	scanf("%d", &t);
	while (t--)
	{
		int n, arr[10], i, j;
		scanf("%d", &n);
		for (i = 0; i < n; i++) 
		{
			scanf("%d", &arr[i]);
		}
		j = (10 - n) * (9 - n) * 3;
		printf("%d\n", j);
	}
	return 0;
}