A straight is a poker hand containing five cards of sequential rank, not necessarily to be the same suit. For example, a hand containing 7 club, 6 spade, 5 spade, 4 heart and 3 diamond forms a straight. In this problem, we extend the definition of a straight to allow 3 to 5 cards of sequential rank. Hence a hand containing K spade, Q club, and J heart is also a straight.

Mr. Panda is playing a poker game called Straight Master. The game uses a large deck of card that has N ranks from 1 to N. The rule of the game is simple: split the cards in Mr. Panda's hand into several straights of length from 3 to 5.

Now given a hand of cards, can you help Mr. Panda to determine if it is possible to split the cards into straights?

Input

The first line of the input gives the number of test cases, T. T test cases follow.

Each test case contains two lines. The first line contains an integer N, indicating the number of ranks in the deck. The next line contains N integers a1, a2, ..., aNindicating the number of cards for each rank in Mr. Panda's hand.

  • 1 ≤ T ≤ 100.
  • 1 ≤ N ≤ 2 × 105.
  • 0 ≤ ai ≤ 109.
  • .

Output

For each test case, output one line containing "Case #x: y", where x is the test case number (starting from 1) and y is Yes if Mr. Panda can split all his cards into straights of length from 3 to 5, or No otherwise.

Example

Input

2
13
1 2 2 1 0 0 0 0 0 0 0 0 0
13
1 1 1 1 0 1 1 0 0 0 0 0 0

Output

Case #1: Yes
Case #2: No

Note

In the first test case, Mr. Panda can split his cards into two straights: [1, 2, 3] and [2, 3, 4]. In the second test case, there is no way to form a straight for card 6 and 7.

题意：

给你一个数组 ， 每次找三到五个连续的数减一 ， 最终使得该数组的每一位都是0.若不能满足则输出no ， 反之yes。

该题也可以翻译成 ， 一个全为0的数组 ， 能否通过区间加1的操作使得他变为题目已给的数组。

思路：

翻译过来就能很容易想到差分的做法吧（反正我没想到）

差分是个好东西 ， 可惜我不会 ，但我晓得找博客 ，啊哈哈哈哈~

 

差分就是将数列中的每一项分别与前一项数做差，例如：

一个序列1 2 5 4 7 3，差分后得到1 1 3 -1 3 -4 -3

这里注意得到的差分序列第一个数和原来的第一个数一样（相当于第一个数减0）

差分序列最后比原序列多一个数（相当于0减最后一个数）

性质：

1、差分序列求前缀和可得原序列

2、将原序列区间[L,R]中的元素全部+1，可以转化操作为差分序列L处+1，R+1处-1

3、按照性质2得到，每次修改原序列一个区间+1，那么每次差分序列修改处增加的和减少的相同


上文转自这里

1 ， 只要找连续数字的个数大于等于3 就可以了 ， 因为大于5的数都可以分解成3，4，5。

2.   差分中正的数与离他最近的负数之间的距离要大于等于3 ， 不然就不符合题意啦。

3.满足上述条件并且 这正的数与负的数相加为0 ， 那就可以得到答案了。

也有这样解释的，

这差分中正的数表示以该数为开头的次数 ， 负的表示以该数为结尾的次数。

徜若在差分相加的过程中就有小于0 的情况 ， 那么一定表示前面有遗留的数字。

下面代码：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5+8;
long long int a[maxn] , b[maxn];
int main()
{
	int t , n ;
	scanf("%d" , &t);
	for(int i = 1 ; i <= t ; i++)
	{
	//	memset(b , 0 , sizeof(b));
		long long int sum = 0;
		scanf("%d" , &n);
		for(int j = 1 ; j <= n ; j++)
		{
			scanf("%lld" , &a[j]);
		}
		a[n+1] = 0;
		for(int j = 1 ; j <= n+1 ; j++)
		{
			b[j] = a[j]-a[j-1];
		}
		if(b[2] < 0 || b[3] < 0)
		{
			printf("Case #%d: No\n" , i);
		}
		else
		{
			for(int j = 1 ; j <= n+1 ; j++)
			{
				if(b[j] >= 0)
				{
					sum += b[j];
				}
				int p = j + 3;
				if(p > n+1)
				{
					break;
				}
				if(b[p] < 0)
				{
					sum += b[p];
				}
				if(sum < 0)
				{
					break;
				}
			}
			if(sum != 0)
			{
				printf("Case #%d: No\n" , i);
			}
			else
			{
				printf("Case #%d: Yes\n" , i);
			}
		}
	
	}
	return 0;
}