2020“远光杯”网络资格赛R 孤独的字符串（dp/容斥）

题目

Luhhy老师最近在研究字符串，只含有字符“a”和“b”的字符串。

她想定义一类串为孤独的串，这类串的特点是串中存在某个字符“a”，它只与“b”相邻或者无相邻字符（比如长度为1的字符串“a”）。

如“babaa”是孤独的串，因为第一个“a”左右两边都是“b”。“aaba”也是，因为最后一个“a”的存在使该串符合条件。

特殊的，一个只含有字符“b“的串不是孤独的串。

现在，给一个正整数n，Luhhy想知道长度为n的孤独的串的数量有多少个。

输入要求 输入数据第一行是一个正整数 T (1