#![allow(bare_trait_objects)]
#![allow(unused_imports)]
#![allow(dead_code)]
#![allow(unused_mut)]

use std::fmt::Debug;
use std::io::BufRead;
use std::io::Stdin;
use std::io::StdinLock;
use std::str::FromStr;

pub struct Scanner<'a> {
    // stdin: Stdin,
    buf_read: Box<BufRead + 'a>,
    tokens: Vec<String>,
}

impl<'a> Scanner<'a> {
    pub fn new(buf_read: StdinLock<'a>) -> Self {
        Scanner {
            buf_read: Box::new(buf_read),
            tokens: Vec::new(),
        }
    }

    // pub fn from_stdin() -> Self {
    //     let stdin = Box::leak(Box::new(std::io::stdin()));
    //     Self {
    //         buf_read: Box::new(stdin.lock()),
    //         tokens: Vec::new(),
    //     }
    // }

    pub fn next(&mut self) -> String {
        while self.tokens.is_empty() {
            let mut s = String::new();
            if self.buf_read.read_line(&mut s).is_err() {
                panic!()
            }
            self.tokens = s
                .split_whitespace()
                .filter(|s| !s.is_empty())
                .rev()
                .map(str::to_string)
                .collect();
        }
        self.tokens.pop().unwrap()
    }

    pub fn next_g<T: FromStr>(&mut self) -> T
    where
        T::Err: Debug,
    {
        self.next().parse().unwrap()
    }

    pub fn next_vec_g<T: FromStr>(&mut self, n: usize) -> Vec<T>
    where
        T::Err: Debug,
    {
        (0..n).map(|_| self.next_g()).collect()
    }

    pub fn usize(&mut self) -> usize {
        self.next_g()
    }

    pub fn i64(&mut self) -> i64 {
        self.next_g()
    }

    pub fn vec_i64(&mut self, n: usize) -> Vec<i64> {
        self.next_vec_g(n)
    }
}

fn solve(mut x1: i64, mut y1: i64, mut x2: i64, mut y2: i64) -> i64 {
    let mut n = 3_i64.pow(29);

    loop {
        if n == 0 {
            return 0;
        }

        // eprintln!("{} {} {} {} {}", x1, y1, x2, y2, n);

        let mut x11 = x1 / n;
        let mut y11 = y1 / n;
        let mut x22 = x2 / n;
        let mut y22 = y2 / n;

        if x11 != x22 && y11 != y22 {
            return (x1 - x2).abs() + (y1 - y2).abs();
        }

        if x11 == x22 && y11 == y22 {
            x1 %= n;
            x2 %= n;
            y1 %= n;
            y2 %= n;
            n /= 3;
            continue;
        }

        if x11 == x22 {
            std::mem::swap(&mut x1, &mut y1);
            std::mem::swap(&mut x2, &mut y2);
            std::mem::swap(&mut x11, &mut y11);
            std::mem::swap(&mut x22, &mut y22);
        }

        if x1 > x2 {
            std::mem::swap(&mut x1, &mut x2);
        }

        loop {
            // eprintln!("{} {} {} {} {} {} {}", x1, x2, y1, y2, n, y11, y22);
            y11 = y2 / n;
            y22 = y1 / n;
            if y11 != y22 {
                return (x1 - x2).abs() + (y1 - y2).abs();
            }
            if y11 == 1 && y22 == 1 {
                if x1 / n + 1 < x2 / n {
                    return (x1 - x2).abs() + std::cmp::min(y1 + y2 - 2 * (n - 1), 4 * n - y1 - y2);
                }
            }
            if n == 1 {
                return (x1 - x2).abs();
            }
            y1 %= n;
            y2 %= n;
            n /= 3;
        }
    }
}

fn main() {
    let stdin = std::io::stdin();
    let mut sc = Scanner::new(stdin.lock());

    let q = sc.usize();
    for _ in 0..q {
        let x1 = sc.i64() - 1;
        let y1 = sc.i64() - 1;
        let x2 = sc.i64() - 1;
        let y2 = sc.i64() - 1;
        println!("{}", solve(x1, y1, x2, y2));
    }
}


Measured memory_bytes: 4476