一来到机房就看到陈指导在做这题，觉得好有趣就一起做了
首先容易看出一个性质，这个(H^x(0))是一个具有斐波那契性质的串，然后和陈指导就一直在想合并的做法，然后直接GG
1h后点开题解，只能大喊妙妙妙（得出结论，我又在混吃等死）
首先看性质，我们来具体地统计一下：
- 斐波那契性质：(H^x=H^{x-1}+H^{x-2})
- 当(2| x)时以(0)结尾，否则以(1)结尾
- 定义(H^{-1}(x))为(H^1(x))的逆操作，不难发现当(s')为(s)字串时，(H^{-1}(s'))仍为(s)字串
再考虑一些不合法的情况：
- 出现(00)必然不合法
- 上一条的推论，出现(111)必然不合法，因为(H^{-1}(111)=00+s)
- 上一条的推论，因为(H(111)=101010=10101+0)，因此对于(xge 5,2 ot | x)时，后缀必然为(10101)，因此此时后面接上(0)必然不合法
然后考虑具体怎么做，我们考虑对于当前的序列({a_1,a_2,cdots,a_{n-1},a_n})
当(min_{iin[1,n]} a_i>0)时我们可以把所有的(a_i-1)，运用了前面的第三条性质
然后我们考虑(0)怎么处理，显然前面是偶数必然不行（不合法1），前面如果是奇数：
- 前面是(1)，那么(1+0=10)，可以合并为(2)
- 前面是(3)，那么(101+0=1010)，可以合并为两个(2)
- 根据不合法3，此时必然无解
然后这样就做完了？交一发就得到了0分的好成绩，Why？
我们考虑对于(11)，显然是合法的，然而被判了不合法（(11 o 00)）
我们仔细分析一波，原因就在于这个结尾的(1)既可以变成(0)也可以变成(1)
那么显然这个(1)不管怎么样都不会影响答案，那么直接把他删了就好
同理开头的(0)由于前面必然是(1)，因此直接转化为(2(10))即可
#include<cstdio>
#define RI register int
#define CI const int&
using namespace std;
const int N=100005;
int t,n,tp,a[N];
int main()
{
for (scanf("%d",&t);t;--t)
{
RI i; bool flag=1; for (scanf("%d",&n),i=1;i<=n;++i)
scanf("%d",&a[i]); while (n>1&&flag)
{
if (!a[1]) a[1]=2; if (a[n]==1) --n; else if (a[n]==3) a[n]=2;
for (i=n;i;--i) if (!a[i])
{
if (a[i-1]==1) a[i-1]=2; else if (a[i-1]==3) a[i-1]=a[i]=2;
else { flag=0; break; }
}
for (tp=0,i=1;i<=n;++i) if (a[i]) a[++tp]=a[i];
for (n=tp,i=1;i<=n;++i) --a[i];
}
puts(flag?"TAK":"NIE");
}
return 0;
}