The first few elements of the sequence are . For a given positive integer , let  be the maximum value of  such that  can be expressed as a sum of  distinct Fibonacci numbers. For example, , , .

Roundgod has an integer  which initially equals . She will perform some operations on . For the -th operation she will add  to .

After each operation, Roundgod wants to know the value of . It is guaranteed that after each operation,  will be a positive integer.

There are multiple test cases. The first line of input contains an integer , indicating the number of test cases. For each test case:

The first line contains an integer  – the number of operations.

Each of the following  lines contains two integers  and  .

It is guaranteed that the sum of  of all test cases  will not exceed .

For each test case, output  integers where the -th integer denotes the value of  after the -th operation.

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

1
1
2
2
3
3
4
4
5
6

The value of  after each operation:1, 2, 4, 7, 12, 20, 33, 54, 88, 72.