use std::time::Instant;
use std::collections::VecDeque;

fn gcd(a: u32, b: u32) -> u32 {
    if b != 0 {
        gcd(b, a % b)
    } else {
        a
    }
}

fn test_naive(n: u32) -> u32 {
    let mut ans = 0;
    for i in 1..n {
        for j in i+1..n {
            if gcd(i, j) == 1 && gcd(i, i + j) == 1 && gcd(j, i + j) == 1 {
                ans += 1;
            }
        }
    }
    ans
}

fn f(a: u32, b: u32, n: u32) -> u32 {
    let mut ans = 0;
    let mut q = VecDeque::new();
    q.push_back((a, b));
    while let Some((x, y)) = q.pop_front() {
        if x < n {
            if gcd(x, x + y) == 1 && gcd(y, x + y) == 1 {
                ans += 1;
            }
            q.push_back((2 * x - y, x));
            q.push_back((2 * x + y, x));
            q.push_back((x + 2 * y, y));
        }
    }
    ans
}

fn test_smart(n: u32) -> u32 {
    f(2, 1, n) + f(3, 1, n)
}

fn main() {
    let n = 10000;

    let now = Instant::now();
    let res = test_naive(n);
    println!("test_naive({}) = {}; done in {:?}", n, res, now.elapsed());

    let now = Instant::now();
    let res = test_smart(n);
    println!("test_smart({}) = {}; done in {:?}", n, res, now.elapsed());
}