fn run(s: &str) -> usize {
    let chars: Vec<char> = s.chars().collect();
    let mut ans = 0;

    for i in 0..s.len() {
        for j in i+1..s.len() {
            for k in j+1..s.len() {
                if j - i == k - j {
                    if chars[i] == 'A' && chars[j] == 'B' && chars[k] == 'C' {
                        ans += 1;
                    }
                }
            }
        }
    }

    ans
}

fn run(_n: usize, a: Vec<usize>) -> usize {
    for i in (0..=100).rev() {
        let mut count = 0;

        for num in a.iter() {
            if *num >= i {
                count += 1;
            }
        }

        if count >= i {
            return i;
        }
    }

    unreachable!();
}

fn run(n: usize, s: usize, m: usize, l: usize) -> usize {
    let mut ans = std::usize::MAX;

    for i in 0..=100 {
        for j in 0..=100 {
            for k in 0..=100 {
                if i*6 + j*8 + k*12 >= n {
                    ans = ans.min(i*s + j*m + k*l);
                }
            }
        }
    }

    ans
}

fn run(n: usize, xy: Vec<(isize, isize)>) -> usize {
    let mut ans = 0;

    for i in 0..n {
        for j in i+1..n {
            for k in j+1..n {
                if (xy[j].0 - xy[i].0)*(xy[k].1 - xy[i].1) - (xy[k].0 - xy[i].0)*(xy[j].1 - xy[i].1) != 0 {
                    ans += 1;
                }
            }
        }
    }

    ans
}

use std::cmp::{min, max};

fn run(x: usize, y: usize) -> f64 {
    let mut count = 0;

    for i in 1..=6 {
        for j in 1..=6 {
            let l = max(i, j);
            let s = min(i, j);

            if i + j >= x || l - s >= y {
                count += 1;
            }
        }
    }

    count as f64 / 36.0
}

fn run(n: usize, m: usize, s: Vec<&str>, t: Vec<&str>) -> (usize, usize) {
    let vec_s: Vec<Vec<char>> = s.into_iter().map(|s| s.chars().collect()).collect();
    let vec_t: Vec<Vec<char>> = t.into_iter().map(|s| s.chars().collect()).collect();

    for i in 0..=n-m {
        for j in 0..=n-m {
            let mut flag = true;

            for k in 0..m {
                for l in 0..m {
                    if vec_s[i+k][j+l] != vec_t[k][l] {
                        flag = false;
                    }
                }
            }

            if flag {
                return (i+1, j+1);
            }
        }
    }

    unreachable!();
}

fn run(s: &str) -> usize {
    let chars: Vec<char> = s.chars().collect();

    let mut ans = 0;

    for i in 0..10000 {
        let str = format!("{:04}", i);

        let mut flags = vec![false; 10];

        for c in str.chars() {
            let i = c.to_digit(10).unwrap();

            flags[i as usize] = true;
        }

        let mut flag = true;

        for j in 0..10 {
            if chars[j] == 'o' && flags[j] == false {
                flag = false;
                break;
            }

            if chars[j] == 'x' && flags[j] {
                flag = false;
                break;
            }
        }

        if flag {
            ans += 1;
        }
    }

    ans
}

fn run(arr: Vec<isize>, a: isize, b: isize, c: isize) -> usize {
    let mut ans = 0;

    let len = arr.len();

    for i in 0..len {
        for j in i+1..len {
            if (arr[i] - arr[j]).abs() > a {
                continue;
            }

            for k in j+1..len {
                if (arr[j] - arr[k]).abs() <= b && (arr[i] - arr[k]).abs() <= c {
                    ans += 1;
                }
            }
        }
    }

    ans
}

fn run(_n: usize, a: Vec<usize>) -> &'static str {
    let mut vec = vec![false; 200_000];

    for i in a {
        vec[i-1] = true;
    }

    for i in 0..200_000-3 {
        if vec[i] == true && vec[i+3] == true && vec[i+6] == true {
            return "Yes";
        }
    }

    "No"
}

use itertools::Itertools;

fn run(_n: usize, a: Vec<isize>) -> Vec<usize> {
    let vec: Vec<isize> = a.clone().into_iter().sorted().collect();

    let min = vec.iter().min().unwrap();
    let max = vec.iter().max().unwrap();

    a.into_iter()
        .map(|i| {
            std::cmp::max((i - *min).abs(), (*max - i).abs()) as usize
        })
        .collect()
}

fn run(n: isize, y: isize) -> Vec<isize> {
    for i in 0..=n {
        for j in 0..=n {
            let k = n - i - j;

            if k < 0 || n < k {
                continue;
            }

            if i * 10000 + j * 5000 + k * 1000 == y {
                return vec![i, j, k];
            }
        }
    }

    vec![-1, -1, -1]
}

fn run(s: &str) -> usize {
    let mut ans = 0;

    let mut vec: Vec<usize> = s.chars()
        .map(|c| {
            match c {
                'a' => 0,
                't' => 1,
                'c' => 2,
                'o' => 3,
                'd' => 4,
                'e' => 5,
                'r' => 6,
                _ => unreachable!(),
            }
        })
        .collect();

    for i in 0..7 {
        let mut flag = true;

        for j in 0..7-i-1 {
            if vec[j] > vec[j+1] {
                vec.swap(j, j+1);
                ans += 1;
                flag = false;
            }
        }

        if flag == true {
            return ans;
        }
    }

    ans
}

use std::cmp::Ordering;

fn upper_bound<T: Ord>(vec: &[T], value: T) -> usize {
    vec.binary_search_by(|x| {
        if *x <= value {
            Ordering::Less
        } else {
            Ordering::Greater
        }
    })
    .err()
    .unwrap()
}

fn run(_n: usize, a: Vec<usize>) -> usize {
    a.iter()
        .map(|x| {
            upper_bound(&a, x/2)
        })
        .sum()
}

use std::cmp::min;

fn check(a: &Vec<usize>, x: usize, m: usize) -> bool {
    let mut total = 0;

    for n in a.iter() {
        total += min(n, &x);
    }

    total <= m
}

fn run(_n: usize, m: usize, a: Vec<usize>) -> String {
    let sum: usize = a.iter().sum();

    if sum <= m {
        return "infinite".to_string();
    }

    let mut l = 0;
    let mut r = std::usize::MAX;

    while l+1 < r {
        let tmp = (l+r)/2;

        if check(&a, tmp, m) == true {
            l = tmp;
        } else {
            r = tmp;
        }
    }

    l.to_string()
}

use itertools::Itertools;

fn run(n: usize, m: usize, a: Vec<usize>) -> usize {
    let a: Vec<usize> = a.into_iter().sorted().collect();

    let mut ans = 0;

    for i in 0..n {
        let upper = a.partition_point(|&x| x < a[i] + m);
        ans = ans.max(upper - i);
    }

    ans
}

fn run(n: usize) -> Vec<usize> {
    let mut ans = Vec::new();

    for i in 1..=(n as f64).sqrt() as usize {
        if n % i == 0 {
            let j = n / i;

            ans.push(i);

            if i != j {
                ans.push(j);
            }
        }
    }

    ans.sort();

    ans
}

fn run(a: usize, b: usize, c: usize, d: usize) -> String {
    let vec = vec![a, b, c, d];

    for bit in 0..(1 << 4) {
        let mut eat = 0;
        let mut rest = 0;

        for i in 0..4 {
            if bit & (1 << i) != 0 {
                eat += vec[i];
            } else {
                rest += vec[i];
            }
        }

        if eat == rest {
            return String::from("Yes");
        }
    }

    String::from("No")
}

fn run(dd: Vec<usize>, jj: Vec<usize>) -> usize {
    let mut ans = 0;

    for bit in 0..(1 << dd.len()) {
        let mut total = 0;

        for i in 0..dd.len() {
            if bit & (1 << i) != 0 {
                total += dd[i];
            } else {
                total += jj[i];
            }
        }

        ans = ans.max(total);
    }

    ans
}

use std::cmp::{min, max};

fn run(n: usize, k: Vec<usize>) -> usize {
    let mut ans = std::usize::MAX;

    for bit in 0..(1 << n) {
        let mut left = 0;
        let mut right = 0;

        for i in 0..n {
            if bit & 1 << i != 0 {
                left += k[i];
            } else {
                right += k[i];
            }
        }

        ans = min(ans, max(left ,right));
    }

    ans
}

fn run(n: usize) -> i32 {
    // 1個も消さずに3で割り切れる場合
    if n % 3 == 0 {
        return 0;
    }

    let mut ans = std::i32::MAX;
    // 各桁をVec<i32>に格納
    let vec: Vec<i32> = n.to_string().chars().map(|c| c.to_digit(10).unwrap() as i32).collect();

    for bit in 1..(1 << vec.len()) {
        // 各桁の合計数
        let mut num = 0;

        // 数値を消した数
        let mut count = 0;

        for i in 0..vec.len() {
            if bit & (1 << i) != 0 {
                num += vec[i] * 10_i32.pow(i as u32);
                count += 1;
            }
        }

        if num % 3 == 0 {
            ans = ans.min(count);
        }
    }

    if ans == std::i32::MAX {
        -1
    } else {
        ans
    }
}

fn run(s: &str) -> String {
    let nums: Vec<i32> = s.chars().map(|c| c.to_digit(10).unwrap() as i32).collect();

    for bit in 0..(1 << 3) {
        // +、-を格納していくVec<char>
        let mut ans = Vec::new();
        // 各数値を+-した合計値
        let mut sum = nums[0];

        for i in 0..3 {
            if bit & (1 << i) != 0 {
                sum += nums[i+1];
                ans.push('+');
            } else {
                sum -= nums[i+1];
                ans.push('-');
            }
        }

        if sum == 7 {
            return format!("{}{}{}{}{}{}{}=7", nums[0], ans[0], nums[1], ans[1], nums[2], ans[2], nums[3]);
        }
    }

    unreachable!();
}

fn run(s: &str) -> usize {
    let len = s.len();
    let chars: Vec<char> = s.chars().collect();

    let mut ans = 0;

    for bit in 0..(1 << len-1) {
        let mut current = chars[0].to_string();
        let mut sum = 0;

        for i in 0..(len-1) {
            if bit & (1 << i) != 0 {
                current.push(chars[i+1]);
            } else {
                sum += current.parse::<usize>().unwrap();
                current = chars[i+1].to_string();
            }
        }

        sum += current.parse::<usize>().unwrap();
        ans+= sum;
    }

    ans
}

fn calc(a: usize, b: usize) -> bool {
    if a == 0 || b == 0 {
        true
    } else if a%10 + b %10 >= 10 {
        false
    } else {
        calc(a/10, b/10)
    }
}

fn run(a: usize, b: usize) -> String {
    if calc(a, b) == true {
        String::from("Easy")
    } else {
        String::from("Hard")
    }
}

fn calc(count: usize, a: usize, b: usize, k: usize) -> usize {
    if a >= b {
        count
    } else {
        calc(count+1, a*k, b, k)
    }
}

fn run(a: usize, b: usize, k: usize) -> usize {
    calc(0, a, b, k)
}

fn calc(n: usize, y: usize, count: usize) -> usize {
    if n > y {
        count
    } else {
        calc(n*2, y, count+1)
    }
}

fn run(x: usize, y: usize) -> usize {
    calc(x, y, 0)
}

fn calc(num: usize, count: usize) -> usize {
    if num % 2 != 0 {
        count
    } else {
        calc(num/2, count+1)
    }
}

fn run(_n: usize, a: vec<usize>) -> usize {
    a.iter()
        .map(|num| {
            // 各要素が2で何回割り切れるかを合計
            calc(*num, 0)
        })
        .sum()
}

fn func(n: usize, s: String, vec: &mut Vec<String>) -> Vec<String> {
    if n == 0 {
        vec.push(s);
        vec.clone()
    } else {
        for c in ["a", "b", "c"].iter() {
            func(n - 1, s.clone() + &c.to_string(), vec);
        }
        vec.clone()
    }
}

fn run(n: usize) -> Vec<String> {
    func(n, "".to_string(), &mut Vec::new())
}

// すぐ書く

use std::collections::HashMap;

fn calc(n: usize, h: &mut HashMap<usize, usize>) -> usize {
    if n < 2 {
        return 0;
    }

    if let Some(x) = h.get(&n) {
        return *x;
    }

    let a = n/2;
    let b = if n % 2 == 0 { n / 2 } else { n / 2 + 1 };

    let num = n + calc(a, h) + calc(b, h);
    h.entry(n).or_insert(num);

    return num;
}

fn run(n: usize) -> usize {
    let mut hash_map: HashMap<usize, usize> = HashMap::new();

    calc(n, &mut hash_map)
}

fn out_of_bounds(h: isize, w: isize, i: isize, j: isize) -> bool {
    i < 0 || j < 0 || i >= h || j >= w
}

fn dfs(vec: &Vec<Vec<char>>, seen: &mut Vec<Vec<bool>>, cur_i: usize, cur_j: usize) {
    seen[cur_i][cur_j] = true;

    let dx = [0, 1, 0, -1];
    let dy = [1, 0, -1, 0];

    for i in 0..4 {
        if out_of_bounds(vec.len() as isize, vec[0].len() as isize, cur_i as isize + dx[i], cur_j as isize + dy[i]) {
            continue;
        }

        let next_i = (cur_i as isize + dx[i]) as usize;
        let next_j = (cur_j as isize + dy[i]) as usize;

        if vec[next_i][next_j] == '#' || seen[next_i][next_j] {
            continue;
        }

        dfs(&vec, seen, next_i, next_j)
    }
}

fn run(h: usize, w: usize, c: Vec<&str>) -> &'static str {
    let vec: Vec<Vec<char>> = c.into_iter().map(|str| str.chars().collect()).collect();

    let mut start = (0, 0);
    let mut end = (0, 0);

    for i in 0..h {
        for j in 0..w {
            if vec[i][j] == 's' {
                start = (i, j);
            }
            if vec[i][j] == 'g' {
                end = (i, j);
            }
        }
    }

    let mut seen = vec![vec![false; w]; h];

    dfs(&vec, &mut seen, start.0, start.1);

    if seen[end.0][end.1] {
        "Yes"
    } else {
        "No"
    }
}

use std::collections::{HashMap, HashSet};

fn dfs(current: usize, seen: &mut HashSet<usize>, graph: &HashMap<usize, Vec<usize>>) -> usize {
    let mut ans = current;
    seen.insert(ans);

    for tmp in graph.get(&current).unwrap() {
        if seen.contains(tmp) {
            continue;
        }

        ans = ans.max(dfs(*tmp, seen, graph));
    }

    ans
}

fn run(_n: usize, ab: Vec<(usize, usize)>) -> usize {
    let mut hash_map: HashMap<usize, Vec<usize>> = HashMap::new();

    for &(a, b) in ab.iter() {
        hash_map.entry(a).or_insert_with(|| Vec::new()).push(b);
        hash_map.entry(b).or_insert_with(|| Vec::new()).push(a);
    }

    // 1階からどこにも行けなかったら1を返す
    let Some(_) = hash_map.get(&1) else {
        return 1;
    };

    dfs(1, &mut HashSet::new(), &hash_map)
}

fn out_of_bounds(h: usize, w: usize, i: isize, j: isize) -> bool {
    i < 0 || j < 0 || h as isize == i || w as isize == j
}

fn dfs(
    h: usize,
    w: usize,
    i: usize,
    j: usize,
    k: usize,
    step: usize,
    grid: &Vec<Vec<char>>,
    visited: &mut Vec<Vec<bool>>,
    count: &mut usize
) {
    if step == k {
        *count += 1;
        return;
    }

    let di = [0, 1, 0, -1];
    let dj = [1, 0, -1, 0];

    for dir_i in 0..4 {
        let new_i = i as isize + di[dir_i];
        let new_j = j as isize + dj[dir_i];

        if out_of_bounds(h, w, new_i, new_j) {
            continue;
        }

        let new_i = new_i as usize;
        let new_j = new_j as usize;

        if visited[new_i][new_j] || grid[new_i][new_j] == '#' {
            continue;
        }

        visited[new_i][new_j] = true;
        dfs(h, w, new_i, new_j, k, step+1, &grid, visited, count);
        visited[new_i][new_j] = false;

    }
}

fn run(h: usize, w: usize, k: usize, s: Vec<&str>) -> usize {
    let vec: Vec<Vec<char>> = s.into_iter().map(|s| s.chars().collect()).collect();

    let mut visited = vec![vec![false; w]; h];

    let mut ans = 0;

    for i in 0..h {
        for j in 0..w {
            if vec[i][j] == '#' {
                continue;
            }

            visited[i][j] = true;
            dfs(h, w, i, j, k, 0, &vec, &mut visited, &mut ans);
            visited[i][j] = false;
        }
    }

    ans
}

use std::collections::HashMap;

fn dfs(
    n: usize,
    hash_map: &HashMap<usize, Vec<(usize, usize)>>,
    seen: &mut Vec<bool>,
    cur: usize,
    xor: usize,
    ans: &mut usize
) {
    seen[cur] = true;

    let Some(next) = hash_map.get(&cur) else {
        return;
    };

    for (w, next) in next {
        if *next == n {
            *ans = (*ans).min(w ^ xor);
            continue;
        }

        if seen[*next] {
            continue;
        }

        dfs(n, hash_map, seen, *next, w ^ xor, ans)
    }

    seen[cur] = false;
}

fn run(n: usize, _m: usize, uvw: Vec<(usize, usize, usize)>) -> usize {
    let mut hash_map = HashMap::new();

    for (u, v, w) in uvw {
        hash_map.entry(u).or_insert_with(|| Vec::new()).push((w, v));
        hash_map.entry(v).or_insert_with(|| Vec::new()).push((w, u));
    }

    let mut seen = vec![false; n+1];

    let mut ans = std::usize::MAX;

    dfs(n, &hash_map, &mut seen, 1, 0, &mut ans);

    ans
}

use std::collections::HashMap;

fn dfs(
    map: &HashMap<&usize, Vec<&usize>>,
    ans: &mut Vec<usize>,
    seen: &mut Vec<bool>,
    current: usize,
    y: usize,
) -> bool {
    if current == y {
        return true;
    }

    for &next in map.get(&current).unwrap_or(&vec![]) {
        if seen[*next] {
            continue;
        }

        seen[*next] = true;
        ans.push(*next);

        if dfs(map, ans, seen, *next, y) {
            return true;
        }

        ans.pop();
    }

    false
}

fn run(n: usize, x: usize, y: usize, uv: Vec<(usize, usize)>) -> Vec<usize> {
    let mut hash_map = HashMap::new();

    for (u, v) in uv.iter() {
        hash_map.entry(u).or_insert_with(|| Vec::new()).push(v);
        hash_map.entry(v).or_insert_with(|| Vec::new()).push(u);
    }

    let mut seen = vec![false; n+1];
    seen[x] = true;

    let mut ans = vec![x];

    dfs(&hash_map, &mut ans, &mut seen, x, y);

    ans
}

use std::collections::VecDeque;

fn run(r: usize, c: usize, s: (usize, usize), g: (usize, usize), v: Vec<&str>) -> usize {
    let vec: Vec<Vec<char>> = v.into_iter().map(|c| c.chars().collect()).collect();

    let mut graph = vec![vec![-1; c]; r];
    let mut queue = VecDeque::new();

    graph[s.0-1][s.1-1] = 0;
    queue.push_back((s.0-1, s.1-1));

    let dx = [0, -1, 0, 1];
    let dy = [-1, 0, 1, 0];

    while queue.len() > 0 {
        let cur = queue.pop_front().unwrap();

        for i in 0..4 {
            let h = (cur.0 as isize + dx[i]) as usize;
            let w = (cur.1 as isize + dy[i]) as usize;

            if vec[h][w] == '#' || graph[h][w] != -1 {
                continue;
            }

            graph[h][w] = graph[cur.0][cur.1] + 1;

            queue.push_back((h, w));
        }
    }

    graph[g.0-1][g.1-1] as usize
}

use std::collections::{HashMap, VecDeque};

fn run(n: usize, _m: usize, ab: Vec<(usize, usize)>) -> Vec<isize> {
    let mut hash_map = HashMap::new();

    for (a, b) in ab {
        hash_map.entry(a-1).or_insert_with(Vec::new).push(b-1);
        hash_map.entry(b-1).or_insert_with(Vec::new).push(a-1);
    }

    let mut graph = vec![-1; n];
    graph[0] = 0;

    let mut queue = VecDeque::new();
    queue.push_back(0);

    while let Some(cur) = queue.pop_front() {
        let Some(next) = hash_map.get(&cur) else {
            continue;
        };

        for next in next.iter() {
            if graph[*next] != -1 {
                continue;
            }

            graph[*next] = graph[cur] + 1;
            queue.push_back(*next);
        }
    }

    graph
}

use std::collections::VecDeque;

fn check(r: isize, c: isize, h: isize, w: isize) -> bool {
    r < 0 || c < 0 || r >= h || c >= w
}

fn run(h: usize, w: usize, s: Vec<&str>) -> usize {
    let mut vec: Vec<Vec<char>> = s.into_iter().map(|s| s.chars().collect()).collect();

    let mut ans = 0;

    let dx = vec![0, 0, -1, 1, -1, -1, 1, 1];
    let dy = vec![-1, 1, 0, 0, -1, 1, -1, 1];

    for i in 0..h {
        for j in 0..w {
            if vec[i][j] == '.' {
                continue;
            }

            ans += 1;

            let mut queue = VecDeque::new();
            queue.push_back((i, j));

            while let Some((cur_i, cur_j)) = queue.pop_front() {
                for i in 0..8 {
                    if check(cur_i as isize + dx[i], cur_j as isize + dy[i], h as isize, w as isize) {
                        continue;
                    }

                    let new_i = (cur_i as isize + dx[i]) as usize;
                    let new_j = (cur_j as isize + dy[i]) as usize;

                    if vec[new_i][new_j] == '#' {
                        vec[new_i][new_j] = '.';
                        queue.push_front((new_i, new_j));
                    }
                }
            }
        }
    }

    ans
}

use std::collections::VecDeque;

fn run(h: usize, w: usize, a: Vec<Vec<usize>>) -> usize {
    let mut queue = VecDeque::new();
    queue.push_back((0, 0, vec![a[0][0]]));

    let dx = [0, 1];
    let dy = [1, 0];

    let mut ans = 0;

    while let Some((cur_i, cur_j, visited)) = queue.pop_front() {
        for i in 0..2 {
            let new_i = cur_i + dx[i];
            let new_j = cur_j + dy[i];

            if new_i == h || new_j == w {
                continue;
            }

            if visited.contains(&a[new_i][new_j]) {
                continue;
            }

            if new_i == h-1 && new_j == w-1 {
                ans += 1;
                continue;
            }

            let mut new_visited = visited.clone();

            new_visited.push(a[new_i][new_j]);

            queue.push_back((new_i, new_j, new_visited));
        }
    }

    ans
}

use std::collections::VecDeque;

fn out_of_bounds(h: usize, w: usize, i: isize, j: isize) -> bool {
    i < 0 || j < 0 || h as isize == i || w as isize == j
}

fn run(h: usize, w: usize, s: Vec<&str>) -> Vec<String> {
    let mut vec: Vec<Vec<char>> = s.into_iter().map(|s| s.chars().collect()).collect();

    let mut queue = VecDeque::new();

    for i in 0..h {
        for j in 0..w {
            if vec[i][j] == 'E' {
                queue.push_back((i, j));
            }
        }
    }

    let di = [0, 1, 0, -1];
    let dj = [1, 0, -1, 0];
    let dis = ['<', '^', '>', 'v'];

    while let Some((cur_i, cur_j)) = queue.pop_front() {
        for i in 0..4 {
            let new_i = cur_i as isize + di[i];
            let new_j = cur_j as isize + dj[i];

            if out_of_bounds(h, w, new_i, new_j) {
                continue;
            }

            let new_i = new_i as usize;
            let new_j = new_j as usize;

            if vec[new_i][new_j] != '.' {
                continue;
            }

            vec[new_i][new_j] = dis[i];

            queue.push_back((new_i, new_j));
        }
    }

    vec.into_iter()
        .map(|v| v.into_iter().collect())
        .collect()
}

use std::collections::VecDeque;

fn check(h: usize, w: usize, i: isize, j: isize) -> bool {
    i < 0 || j < 0 || i == h as isize || j == w as isize
}

fn run(h: usize, w: usize, s: Vec<&str>) -> &'static str {
    let str = ['s', 'n', 'u', 'k', 'e'];
    let chars: Vec<Vec<char>> = s.into_iter().map(|s| s.chars().collect()).collect();

    let mut dist = vec![vec![false; w]; h];

    let mut queue = VecDeque::new();
    queue.push_back(((0, 0), 0));

    let dx = [0, 1, 0, -1];
    let dy = [1, 0, -1, 0];

    while let Some(((cur_i, cur_j), count)) = queue.pop_front() {
        if &str[count % 5] != &chars[cur_i][cur_j] || dist[cur_i][cur_j] {
            continue;
        }

        if cur_i == h-1 && cur_j == w-1 {
            return "Yes";
        }

        dist[cur_i][cur_j] = true;

        for i in 0..4 {
            let new_i = cur_i as isize +  dx[i];
            let new_j = cur_j as isize +  dy[i];

            if check(h, w, new_i, new_j) {
                continue;
            }

            queue.push_back(((new_i as usize, new_j as usize), count+1));
        }
    }

    "No"
}

use std::collections::VecDeque;

fn check(r: isize, c: isize) -> bool {
    r < 0 || c < 0 || r >= 2001 || c >= 2001
}

fn run(_n: usize, xy: Vec<(isize, isize)>) -> usize {
    let offset = 1000;

    let xy: Vec<(isize, isize)> = xy.into_iter().map(|(x, y)| (x+offset, y+offset)).collect();

    let mut vec = vec![vec![false; 2001]; 2001];

    for (x, y) in xy.iter() {
        vec[*x as usize][*y as usize] = true;
    }

    let dx = [0, 1, 1, 0, -1, -1];
    let dy = [1, 1, 0, -1, -1, 0];

    let mut ans = 0;

    for (x, y) in xy.iter() {
        if !vec[*x as usize][*y as usize] {
            continue;
        }

        ans += 1;

        let mut queue = VecDeque::new();

        queue.push_back((*x, *y));

        while let Some((cur_i, cur_j)) = queue.pop_front() {
            if !vec[cur_i as usize][cur_j as usize] {
                continue;
            }

            vec[cur_i as usize][cur_j as usize] = false;

            for i in 0..6 {
                if check(cur_i as isize + dx[i], cur_j as isize + dy[i]) {
                    continue;
                }

                let new_i = (cur_i as isize + dx[i]) as usize;
                let new_j = (cur_j as isize + dy[i]) as usize;

                if vec[new_i][new_j] {
                    queue.push_back((new_i as isize, new_j as isize));
                }
            }
        }
    }

    ans
}

use std::collections::{HashMap, VecDeque};

fn run(_n: usize, _m: usize, ab: Vec<(usize, usize)>) -> isize {
    let mut hash_map = HashMap::new();

    for (a, b) in ab {
        hash_map.entry(a).or_insert_with(|| Vec::new()).push(b);
    }

    let mut queue = VecDeque::new();
    queue.push_back((1, 0));

    while let Some((cur, count)) = queue.pop_front() {
        let Some(next) = hash_map.get(&cur) else {
            continue;
        };

        for next in next.iter() {
            if *next == 1 {
                return count + 1;
            }

            queue.push_back((*next, count+1));
        }
    }

    -1
}

use std::collections::VecDeque;

fn check(i: isize, j: isize, h: isize, w: isize) -> bool {
    i < 0 || j < 0 || i == h || j == w
}

fn run(h: usize, w: usize, d: usize, s: Vec<&str>) -> usize {
    let vec: Vec<Vec<char>> = s.into_iter().map(|s| s.chars().collect()).collect();

    let mut graph = vec![vec![-1; w]; h];
    let mut queue = VecDeque::new();

    for i in 0..h {
        for j in 0..w {
            if vec[i][j] == 'H' {
                queue.push_back((i, j));
                graph[i][j] = 0;
            }
        }
    }

    let dx = [0, 1, 0, -1];
    let dy = [1, 0, -1, 0];

    while let Some((cur_i, cur_j)) = queue.pop_front() {
        if d == 0 {
            continue;
        }

        for i in 0..4 {
            let new_i = cur_i as isize + dx[i];
            let new_j = cur_j as isize + dy[i];

            if check(new_i, new_j, h as isize, w as isize) {
                continue;
            }

            let new_i = new_i as usize;
            let new_j = new_j as usize;

            if vec[new_i][new_j] == '#' || graph[new_i][new_j] != -1 {
                continue;
            }

            graph[new_i][new_j] = graph[cur_i][cur_j] + 1;

            queue.push_back((new_i, new_j));
        }
    }

    graph.into_iter()
        .map(|g| {
            g.into_iter()
                .filter(|i| {
                    *i >= 0 && *i <= d as isize
                })
                .count()
        })
        .sum()
}