2700：递归了几次？

在学习斐波那契数列后，大家不难写出这样一份递归的代码：

int f(int n)
{
	if (n <= 2)
	{
		return 1;
	}
	return f(n - 1) + f(n - 2);
}

今天罗少想考考大家，若添加一个全局变量$$cnt$$以计数，那么在进行一次$$f(x)$$后，$$cnt$$的值为多少？

int cnt = 0;
int f(int n)
{
	cnt = (cnt + 1) % 1000000007;
	if (n <= 2)
	{
		return 1;
	}
	return f(n - 1) + f(n - 2);
}

第一行是一个正整数$$T$$表示测试案例的数量。($$1 \leq T \leq 10^5$$)

每组案例包含一个正整数$$x$$含义如描述。($$1 \leq x \leq 10^5$$)

针对每组案例，输出在进行一次$$f(x)$$的调用后，$$cnt$$的值为多少？

这里假设每组案例都是独立的，即每次调用完$$f(x)$$后，$$cnt$$自动清零。

5

1

3

5

8

10

1

3

9

41

109

题单#18（递推与记忆化搜索）