斐波那契字符串 是一个仅由 与 构成的字符串，定义如下： ； ； 对于任意整数 ，，其中 表示字符串拼接。 例如：、、。 在字符串 中，如果存在一对下标 满足 且 、，则称 为一次逆序对。 现在给定若干组测试数据，每组数据给出一个正整数 。对于每组数据，请你求出字符串 中逆序对的数量。由于答案可能很大，请对 取模后输出。 【名词解释】 斐波那契字符串：由 与 递推得到的字符串序列，递推规则见题目描述； 逆序对：在序列或字符串中，若存在下标 且对应元素满足 a_j" ，则 构成一对逆序对。此题中特指 、 的情况。

输入描述:

每个测试文件均包含多组测试数据。第一行输入一个整数 代表数据组数，每组测试数据描述如下： 每组测试数据，在一行上输入一个整数 ，代表要生成的斐波那契字符串的编号。

输出描述:

对于每一组测试数据，在一行上输出一个整数，代表 中逆序对的数量对 取模后的结果。