斐波那契数列定义如下：

$$ F_n = \begin{cases} 1 & n = 1 \\ 2 & n = 2 \\ F_{n-1} + F_{n-2} & \text{其他情况} \end{cases} $$

该数列的前几项为 $1, 2, 3, 5, 8, 13, 21, 34, \dots$

对于给定的正整数 $n$，令 $partition(n)$ 为 $n$ 能表示为 $m$ 个不同的斐波那契数之和时，$m$ 的最大值。例如，$partition(1) = partition(2) = 1$，$partition(3) = partition(4) = partition(5) = partition(7) = 2$，$partition(6) = partition(8) = 3$。

Chiaki 有一个初始值为 $0$ 的整数 $X$。她将对 $X$ 进行若干次操作：第 $i$ 次操作会将 $a_i \cdot F_{b_i}$ 加到 $X$ 上。

每次操作后，Chiaki 想知道 $partition(X)$ 的值。保证每次操作后，$X$ 均为正整数。

输入格式

输入包含多组测试数据。第一行包含一个整数 $T$，表示测试数据的组数。对于每组测试数据：

第一行包含一个整数 $n$ ($1 \le n \le 5 \cdot 10^4$)，表示操作次数。

接下来的 $n$ 行，每行包含两个整数 $a_i$ 和 $b_i$ ($1 \le |a_i|, b_i \le 10^9$)。

保证所有测试数据的 $n$ 之和不超过 $5 \cdot 10^4$。

输出格式

对于每组测试数据，输出 $n$ 个整数：第 $i$ 个整数表示第 $i$ 次操作后 $partition(X)$ 的值。

样例

输入 1

1
10
1 1
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
-2 5

输出 1

1
1
2
2
3
3
4
4
5
6

说明

样例中每次操作后 $X$ 的值分别为：$1, 2, 4, 7, 12, 20, 33, 54, 88, 72$。