피보나치 분할

피보나치 수열은 다음과 같이 정의된다: F_n=\\begin{cases} 1 & n=1 \\\\ 2 & n=2 \\\\ F_{n-1}+F_{n-2} & \\text{otherwise} \\end{cases}

수열의 처음 몇 개 원소는 $1, 2, 3, 5, 8, 13, 21, 34, \\dots$ 이다.

양의 정수 $n$에 대해 $\\mathit{partition}(n)$은 $n$을 서로 다른 피보나치 수 $m$개의 합으로 나타낼 수 있는 $m$의 최댓값이다. 예를 들어 $\\mathit{partition}(1) = \\mathit{partition}(2) = 1$, $\\mathit{partition}(3) = \\mathit{partition}(4) = \\mathit{partition}(5) = \\mathit{partition}(7) = 2$, $\\mathit{partition}(6) = \\mathit{partition}(8) = 3$이다.

Chiaki는 처음에 0인 정수 $X$를 가지고 있다. 그녀는 $X$에 대해 여러 번 연산을 수행한다. $i$번째 연산은 $a_i \\cdot F_{b_i}$를 $X$에 더한다. 매 연산 후 $\\mathit{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$번째 연산 후 $\\mathit{partition}(X)$의 값이다.

예시에서 각 연산 후 $X$의 값은 $1, 2, 4, 7, 12, 20, 33, 54, 88, 72$이다.