public class Solution {
    public static int commonPrimeDivisors(int[] a, int[] b) {
        int counter = 0;

        for (int i = 0; i < a.length; i++) {
            int x = a[i];
            int y = b[i];
            int d = gcd(x, y);

            x = removeCommonPrimeDivisors(x, d);
            if (x != 1) {
                continue;
            }

            y = removeCommonPrimeDivisors(y, d);
            if (y == 1) {
                counter++;
            }
        }

        return counter;
    }

    private static int gcd(int n, int m) {
        if (n % m == 0) {
            return m;
        }

        return gcd(m, n % m);
    }

    private static int removeCommonPrimeDivisors(int n, int m) {
        while (n != 1) {
            int d = gcd(n, m);
            if (d == 1) {
                break;
            }
            n /= d;
        }

        return n;
    }
}

(defun cpd-gcd (n m)
  (if (zerop (mod n m))
      m
      (cpd-gcd m (mod n m))))

(defun remove-common-prime-divisors (n m)
  (loop while (/= n 1)
        do (let ((d (cpd-gcd n m)))
             (when (= d 1)
               (return-from remove-common-prime-divisors n))
             (setf n (/ n d))))
  n)

(defun common-prime-divisors (a b)
  (let ((counter 0))
    (loop for x in a
          for y in b
          do (let* ((d (cpd-gcd x y))
                     (rx (remove-common-prime-divisors x d)))
               (when (= rx 1)
                 (let ((ry (remove-common-prime-divisors y d)))
                   (when (= ry 1)
                     (incf counter))))))
    counter))

function commonPrimeDivisors(array $a, array $b): int
{
    $gcd = static function (int $n, int $m) use (&$gcd) {
        if ($n % $m === 0) {
            return $m;
        }

        return $gcd($m, $n % $m);
    };

    $removeCommonPrimeDivisors = static function (int $n, int $m) use ($gcd) {
        while ($n !== 1) {
            $d = $gcd($n, $m);
            if ($d === 1) {
                break;
            }
            $n /= $d;
        }

        return $n;
    };

    $counter = 0;
    for ($i = 0, $count = count($a); $i < $count; $i++) {
        $x = $a[$i];
        $y = $b[$i];
        $d = $gcd($x, $y);

        $x = $removeCommonPrimeDivisors($x, $d);
        if ($x !== 1) {
            continue;
        }

        $y = $removeCommonPrimeDivisors($y, $d);
        if ($y === 1) {
            $counter++;
        }
    }

    return $counter;
}

from math import gcd


def common_prime_divisors(a: list[int], b: list[int]) -> int:
    def remove_common_prime_divisors(n: int, m: int) -> int:
        while n != 1:
            d = gcd(n, m)
            if d == 1:
                break
            n //= d
        return n

    counter = 0
    for x, y in zip(a, b):
        d = gcd(x, y)

        x = remove_common_prime_divisors(x, d)
        if x != 1:
            continue

        y = remove_common_prime_divisors(y, d)
        if y == 1:
            counter += 1

    return counter

fn gcd(n: i64, m: i64) -> i64 {
    if n % m == 0 { m } else { gcd(m, n % m) }
}

fn remove_common_prime_divisors(mut n: i64, m: i64) -> i64 {
    while n != 1 {
        let d = gcd(n, m);
        if d == 1 {
            break;
        }
        n /= d;
    }

    n
}

fn common_prime_divisors(a: &[i64], b: &[i64]) -> i64 {
    let mut counter = 0;
    for i in 0..a.len() {
        let x = a[i];
        let y = b[i];
        let d = gcd(x, y);

        let x = remove_common_prime_divisors(x, d);
        if x != 1 {
            continue;
        }

        let y = remove_common_prime_divisors(y, d);
        if y == 1 {
            counter += 1;
        }
    }

    counter
}

function commonPrimeDivisors(a: number[], b: number[]): number {
  const gcd = (n: number, m: number): number => (n % m === 0 ? m : gcd(m, n % m));

  const removeCommonPrimeDivisors = (n: number, m: number): number => {
    while (n !== 1) {
      const d = gcd(n, m);
      if (d === 1) {
        break;
      }
      n /= d;
    }

    return n;
  };

  let counter = 0;
  for (let i = 0; i < a.length; i++) {
    let x = a[i];
    let y = b[i];
    const d = gcd(x, y);

    x = removeCommonPrimeDivisors(x, d);
    if (x !== 1) {
      continue;
    }

    y = removeCommonPrimeDivisors(y, d);
    if (y === 1) {
      counter++;
    }
  }

  return counter;
}

count_div() {
    local _a=$1 _b=$2 _k=$3
    local _firstDiv
    if (( _a % _k == 0 )); then _firstDiv=$_a; else _firstDiv=$(( _a + (_k - _a % _k) )); fi
    local _lastDiv=$(( _b - _b % _k ))
    echo $(( (_lastDiv - _firstDiv) / _k + 1 ))
}

long long countDiv(long long a, long long b, long long k)
{
    long long firstDiv = a % k == 0 ? a : a + (k - a % k);
    long long lastDiv = b - b % k;

    return (lastDiv - firstDiv) / k + 1;
}

static long CountDiv(long a, long b, long k)
{
    var firstDiv = a % k == 0 ? a : a + (k - a % k);
    var lastDiv = b - b % k;

    return (lastDiv - firstDiv) / k + 1;
}

defmodule CountDiv do
  def count_div(a, b, k) do
    first_div = if rem(a, k) == 0, do: a, else: a + (k - rem(a, k))
    last_div = b - rem(b, k)

    div(last_div - first_div, k) + 1
  end
end