// Not afraid to dark.

#include <bits/stdc++.h>
using namespace std;

clock_t start_time, end_time;
#define GET_START start_time = clock ();
#define GET_END end_time = clock (); fprintf (stderr, "TIME COSSEMED : %0.3lf\n", 1.0 * (end_time - start_time) / CLOCKS_PER_SEC);

#define int long long

namespace io {
    int read_pos, read_dt; char read_char;
    __inline__ __attribute__ ((always_inline)) int read (int &p = read_pos){
        p = 0, read_dt = 1; read_char = getchar ();
        while (! isdigit (read_char)){
            if (read_char == '-')
                read_dt = - 1;
            read_char = getchar ();
        }
        while (isdigit (read_char)){
            p = (p << 1) + (p << 3) + read_char - 48;
            read_char = getchar ();
        }
        return p = p * read_dt;
    }
    int write_sta[65], write_top;
    __inline__ __attribute__ ((always_inline)) void write (int x){
        if (x < 0)
            putchar ('-'), x = - x;
        write_top = 0;
        do
            write_sta[write_top ++] = x % 10, x /= 10;
        while (x);
        while (write_top)
            putchar (write_sta[-- write_top] + 48);
    }
    int llen;
    __inline__ __attribute__ ((always_inline)) int get_string (char c[], int &len = llen){
        len = 0;
        read_char = getchar ();
        while (read_char == ' ' || read_char == '\n' || read_char == '\r')
            read_char = getchar ();
        while (read_char != ' ' && read_char != '\n' && read_char != '\r'){
            c[++ len] = read_char;
            read_char = getchar ();
        }
        return len;
    }
}

#define vic(x) (((x) & 1) ? - 1 : 1)

const int V = 1e9, inf = 0x3f3f3f3f3f3f3f3fll;

int Luc[105], cnt;
int Fib[105];

__inline__ __attribute__ ((always_inline)) void INIT (){
    Luc[0] = 2;
    Luc[1] = 1;
    for (cnt = 1;Luc[cnt] <= V;++ cnt)
        Luc[cnt + 1] = Luc[cnt] + Luc[cnt - 1];
    -- cnt;
    // Fib[1] = 1;
    // for (int i = 2;i <= 56;++ i)
    //     Fib[i] = Fib[i - 1] + Fib[i - 2];
}

int ans;

struct node {
    int l, r;
    node (int _l_ = 0, int _r_ = 0){
        l = _l_;
        r = _r_;
    }
    __inline__ __attribute__ ((always_inline)) bool operator < (const node &oth) const {
        if (l == oth.l)
            return r < oth.r;
        return l < oth.l;
    }
};

set < node > s;

namespace CHECK {
    __inline__ __attribute__ ((always_inline)) void OUTPUT (){
        printf ("<%lld>", ans);
        int sum = 0;
        for (auto x : s){
            printf ("[%lld %lld]", x.l, x.r);
            for (int i = x.l;i <= x.r;i += 2){
                sum += Fib[i];
                // printf ("<<%lld>>", Fib[i - 1]);
            }
        }
        printf (">> %lld", sum);
        puts ("");
    }
}

__inline__ __attribute__ ((always_inline)) set < node > ::iterator find_right (int x){
    return s.upper_bound (node (x, inf));
}
__inline__ __attribute__ ((always_inline)) set < node > ::iterator find_contain (int x){
    auto it = find_right (x);
    if (it == s.begin ())
        return s.end ();
    -- it;
    if ((*it).r >= x)
        return it;
    return s.end ();
}
__inline__ __attribute__ ((always_inline)) set < node > ::iterator find_left (int x){
    auto it = find_right (x);
    if (it != s.begin ())
        -- it;
    if (it == s.end ())
        return it;
    if ((*it).r >= x && it != s.begin ())
        return -- it;
    if (it == s.begin () && (*it).r >= x)
        return s.end ();
    return it;
}

// __inline__ __attribute__ ((always_inline)) bool Check_first (node x){
//     return find_left (x.l) == s.end ();
// }

__inline__ __attribute__ ((always_inline)) int Cost (node x){ // self cost
    if (x.l <= 3)
        return ((x.r - x.l) >> 1);
    return x.r - x.l;
}

__inline__ __attribute__ ((always_inline)) int Cost_con (node x, node y){ // connect cost
    int las = x.r - 1;
    if (x.l <= 3)
        ++ las;
    if (y.l - las <= 2)
        return 1;
    return (y.l - las + 1) / 2;
}

__inline__ __attribute__ ((always_inline)) void Del (node x){
    if (x.l > x.r)
        return ;
    auto bel = find_contain (x.l);
    node tt = *bel;
    s.erase (bel);
    if (tt.l <= x.l - 2)
        s.insert (node (tt.l, x.l - 2));
    if (x.r + 2 <= tt.r)
        s.insert (node (x.r + 2, tt.r));
    auto pre = find_left (x.l);
    // printf ("del : %lld %lld\n", x.l, x.r);
    // printf ("before : "); CHECK::OUTPUT ();
    if (pre != s.end ())
        ans -= Cost_con (*pre, x);
    else
        ans -= Cost_con (node (1, 1), x);
    auto nex = find_right (x.r);
    if (nex != s.end ())
        ans -= Cost_con (x, *nex);
    // CHECK::OUTPUT ();
    if (pre != s.end () && nex != s.end ())
        ans += Cost_con (*pre, *nex);
    else
    if (nex != s.end ())
        ans += Cost_con (node (1, 1), *nex);
    // CHECK::OUTPUT ();
    ans -= Cost (x);
    // CHECK::OUTPUT ();
    // puts ("del end");
}
void Ins (node x){
    if (x.l > x.r)
        return ;
    auto pre = find_left (x.l), nex = find_right (x.r);
    // printf ("ins : %lld %lld\n", x.l, x.r);
    if (pre != s.end () && (*pre).r == x.l - 2){
        node tt;
        Del (tt = *pre);
        Ins (node (tt.l, x.r));
        return ;
    }
    if (nex != s.end () && (*nex).l == x.r + 2){
        node tt;
        Del (tt = *nex);
        Ins (node (x.l, tt.r));
        return ;
    }
    // printf ("ins : %lld %lld\n", x.l, x.r);
    // printf ("before : ");
    // CHECK::OUTPUT ();
    if (pre != s.end ())
        ans += Cost_con (*pre, x);
    else
        ans += Cost_con (node (1, 1), x);
    // CHECK::OUTPUT ();
    if (nex != s.end ())
        ans += Cost_con (x, *nex);
    if (pre != s.end () && nex != s.end ())
        ans -= Cost_con (*pre, *nex);
    else
    if (nex != s.end ())
        ans -= Cost_con (node (1, 1), *nex);
    ans += Cost (x);
    s.insert (x);
    // CHECK::OUTPUT ();
    // puts ("ins end");

}


void Insert (int v, int p){
    if (p < 1)
        return ;
    if (p == 1){
        Insert (v, 2);
        return ;
    }
    // printf ("<%lld %lld>\n", v, p);
    if (v == 1){
        set < node > ::iterator it;
        if ((it = find_contain (p)) != s.end ()){
            node tt = *it;
            if ((p & 1) == (tt.l & 1)){
                Del (tt);
                Ins (node (tt.l + 1, p - 1));
                Insert (1, tt.r + 1);
                Insert (1, tt.l - 2);
            } else {
                Del (tt);
                Ins (node (tt.l, p - 1));
                Insert (1, tt.r + 1);
            }
        } else
        if ((it = find_left (p)) != s.end () && (*it).r == p - 1){
            node tt = *it;
            Del (tt);
            Ins (node (tt.l, tt.r - 2));
            Insert (1, tt.r + 2);
        } else
        if ((it = find_right (p)) != s.end () && (*it).l == p + 1){
            // puts ("in");
            node tt = *it;
            Del (tt);
            Insert (1, tt.r + 1);
        } else
            Ins (node (p, p));
    } else {
        set < node > ::iterator it;
        if ((it = find_contain (p)) != s.end ()){
            node tt = *it;
            if ((p & 1) == (tt.l & 1)){
                Del (tt);
                Ins (node (tt.l, p - 2));
                Ins (node (p + 2, tt.r));
            } else {
                Insert (- 1, p + 1);
                Insert (1, p - 1);
            }
        } else {
            // exist prefix 
            it = find_right (p);
            node tt = *it;
            // CHECK::OUTPUT ();
            Del (tt);
            // CHECK::OUTPUT ();
            Ins (node (tt.l + 2, tt.r));
            int tl = tt.l - 1, u = p + 1;
            if ((u & 1) != (tl & 1))
                ++ u;
            Ins (node (u, tl));
            if (u != p + 1)
                Insert (1, p - 1);
        }
    }
}

__inline__ __attribute__ ((always_inline)) void WORK (){
    // int sum = 0, res = 0;
    for (int T = io::read (), x, y;T --;){
        io::read (x), io::read (y);
        ++ y;
        // sum += x * Fib[y];
        if (! x)
            goto put_ans;
        // Insert (x, y);
        // goto put_ans;
        {
            int v = x / abs (x);
            x = abs (x);
            // int sm = 0;
            for (int i = cnt;i > 1;-- i)
                if (Luc[i] <= x){
                    x -= Luc[i];
                    if (v > 0){
                        Insert (v, y + i);
                        Insert (v * vic (i) * vic ((y - i < 0 ? (i - y + 1) : 0)), abs (y - i));
                    } else {
                        Insert (v * vic (i) * vic ((y - i < 0 ? (i - y + 1) : 0)), abs (y - i));
                        Insert (v, y + i);
                    }
                    // res += v * Fib[y + i] + v * vic (i) * vic ((y - i < 0) ? (i - y + 1) : 0) * Fib[abs (y - i)];
                    // sm += Luc[i];
                }
            // printf ("%lld %lld\n", res, sm);
            for (int i = 0;i < 2;++ i)
                if (Luc[i] <= x){
                    x -= Luc[i];
                    if (v > 0){
                        Insert (v, y + i);
                        // if (y == 6)
                        //     printf ("%lld %lld : ", v * vic (i), abs (y - i)), CHECK::OUTPUT ();
                        Insert (v * vic (i) * vic ((y - i < 0 ? (i - y + 1) : 0)), abs (y - i));
                        // if (y == 6)
                        //     printf ("%lld %lld : ", v, y + i), CHECK::OUTPUT ();
                    } else {
                        Insert (v * vic (i) * vic ((y - i < 0 ? (i - y + 1) : 0)), abs (y - i));
                        // if (y == 6)
                        //     printf ("%lld %lld : ", v * vic (i), abs (y - i)), CHECK::OUTPUT ();
                        Insert (v, y + i);
                        // if (y == 6)
                        //     printf ("%lld %lld : ", v, y + i), CHECK::OUTPUT ();
                    }
                    // res += v * Fib[y + i] + v * vic (i) * vic ((y - i < 0 ? (i - y + 1) : 0)) * Fib[abs (y - i)];
                }
            // printf ("rest : %lld\n", x);
            if (! s.empty () && (*s.begin ()).l == 1)
                Del (node (1, 1)), Insert (1, 2);
        }
        put_ans : ;
        // CHECK::OUTPUT ();
        io::write (ans), puts ("");
    }
}

__inline__ __attribute__ ((always_inline)) void init (){
    s.clear ();
    ans = 0;
}

signed main (){

    GET_START

    INIT ();
    for (int T = io::read ();T --;)
        WORK (), init ();
    
    GET_END

    return 0;
}
/*
ex : 

in:
3
6
912254245 4
-1 46
-12 36
893871732 9
803228012 6
-2420954 6
1
84415313 5
8
968295352 9
61184346 7
461451639 3
678826278 4
108032410 3
515272015 4
879628340 3
85675803 7

out:
34
32
34
36
40
36
31
40
36
34
35
?

example :

input : 
1
19
1 1
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
-2 5
2 5
-1 8
-1 7
-1 6
-1 5
-1 4
-1 3
-1 2
-1 1

output : 
1
1
2
2
3
3
4
4
5
6
5
4
4
3
3
2
2
1

*/

// 1 2 1 2 1 2