lab2_queue.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "   #  MP307 Practical 2 Queueing Theory II"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Python functions for queue analysis\n",
    "\n",
    "The Python functions contained in this notebook are:\n",
    "\n",
    "1. `Nearneigh(pup,pdown,r)`. This generates the transition matrix $P$ stored in `P` for a simple nearest neighbour model with maximum size `r` and probability `pup` of one step up transition and  `pdown` for one step down transition. The output is the transition matrix.\n",
    "\n",
    "2. `Equilibrium(P)`. This computes the equilibrium probabilities for a given transition matrix `P`. If the system is not ergodic then an error message appears. The output is an array.\n",
    "\n",
    "3. `Queue(P,n0,nit)`. This simulates a queue for a given transition matrix `P` with initial queue size `n0` for `nit`  iterations. The output is a list of simulated queue data.\n",
    "\n",
    "4. `Qplot(qdata,pi)`. `Qplot(qdata)` generates a histogram of the frequencies of the observed queue sizes in the input data list `qdata`. The second argument is optional and refers to the equilibrium probabilities `pi` (if they exist and have been calculated via `Equilibrium(P)` above or otherwise). The output of `Qplot(qdata,pi)` is the frequency histogram together with a plot of the equilibrium probabilities `pi`. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%matplotlib inline\n",
    "\n",
    "import numpy as np\n",
    "import math\n",
    "import matplotlib.pyplot as plt\n",
    "import matplotlib.patches as patches\n",
    "import matplotlib.path as path\n",
    "import matplotlib.animation as animation\n",
    "from matplotlib.patches import Rectangle\n",
    "import random as ran"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def Nearneigh (pup, pdown, r):\n",
    "    # This generates the transition matrix P for a nearest neighbour model with \n",
    "    # maximum size r and probability pup of one step up transition and pdown \n",
    "    # for one step down transition. \n",
    "    # The output is the transition matrix P.\n",
    "    P = np.zeros((r + 1, r + 1))\n",
    "    P[0, 0] = 1 - pup\n",
    "    P[0, 1] = pup\n",
    "    P[r , r ] = 1 - pdown\n",
    "    P[r , r - 1] = pdown\n",
    "    for i in range(1, r):\n",
    "        P[i, i - 1] = pdown\n",
    "        P[i , i] = 1 - pdown - pup\n",
    "        P[i , i + 1] = pup\n",
    "    return(P)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Example. \n",
    "Find the transition matrix for a queue of maximum size 5 with prob customer arrival=0.2 and prob customer servicing=0.3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "P=Nearneigh(0.2,0.3,5)\n",
    "print(P)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def Equilibrium (P):\n",
    "    # This computes the equilibrium probabilities pi for a given transition matrix P. \n",
    "    # If the system is not ergodic then an error message appears. \n",
    "    # The output is an array.\n",
    "    degenflag = 0\n",
    "    n = len(P)\n",
    "    pi = np.zeros((n))\n",
    "    for i in range(n):\n",
    "        if float(sum(P[i,:]))!= 1.0:\n",
    "            print(\"ERROR: row\",i,\"of P does not sum to 1 !\")\n",
    "    eigenvals, eigenvects=np.linalg.eig(P.transpose()) # eigendata for P transpose\n",
    "    for k in range(n):\n",
    "        if abs(eigenvals[k]-1)< 1.0e-14:\n",
    "            degenflag = degenflag + 1\n",
    "            k1=k # label for eigenvalue 1.\n",
    "    if 1 < degenflag:\n",
    "        print(\"ERROR: P is not Ergodic\")\n",
    "    else:\n",
    "        v=eigenvects[:,k1]\n",
    "        pi=v/sum(v)\n",
    "    return(pi.real)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "pi=Equilibrium(P)\n",
    "print(pi)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def Queue (P, n0, nit):\n",
    "# This simulates a queue for a given transition matrix P with initial queue size n0 for nit iterations. \n",
    "# The output is a list of simulated queue data.\n",
    "    nP = len(P)\n",
    "# pp is a relabelled transition matrix with row elements in decreasing order.\n",
    "# This is used to speed up the simulation process\n",
    "# The relabelling is stored in the matrix loc.\n",
    "    pp = np.zeros((nP,nP))\n",
    "    for i in range(nP):\n",
    "        for j in range(nP):\n",
    "            pp[i, j] = P[i, j]\n",
    "    loc = np.array([list(range(nP))]*nP)\n",
    "    for i in range(nP):\n",
    "        for j in range(nP-1):\n",
    "            maxpp = pp[i, j]\n",
    "            kmax = j\n",
    "            for k in range(j, nP):\n",
    "                if maxpp < pp[i, k]:\n",
    "                    maxpp = pp[i, k]\n",
    "                    kmax = k\n",
    "                    pp[i, j], pp[i, k] = pp[i, k], pp[i, j]\n",
    "                    loc[i, j], loc[i, k] = loc[i, k], loc[i, j]\n",
    "    n = n0\n",
    "    qseq = [n0]\n",
    "    if n0 < 0 or nP-1 < n0:\n",
    "        print(\"ERROR: inputted initial Q size : Qsize<0 or Qsize>\",nP-1)\n",
    "    for m in range(nit):\n",
    "        x = ran.random() # generates uniform random no on [0,1] \n",
    "        k = 0\n",
    "        x1 = pp[n, k]\n",
    "        while (x1 < x):\n",
    "            k = k + 1\n",
    "            x1 = x1 + pp[n, k]\n",
    "        n = loc[n, k] \n",
    "        qseq = qseq + [n]\n",
    "    return(qseq)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(P) # For the transition matrix in our example above"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Simulate 1000 steps with intial state 2 for given P"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "qdata=Queue(P,2,1000) \n",
    "print(qdata)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "len(qdata) # notice there are 1001 data pts for 1000 steps"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def Qplot(qdata,pi=0):\n",
    "    Npoints=len(qdata)\n",
    "    qmax=max(qdata)\n",
    "\n",
    "    #histogram bins\n",
    "    shift = lambda x: x-1/2    \n",
    "    inbins=list(map(shift,list(range(qmax+2)))) # bins -1/2,1/2,3/2,...\n",
    "    n,bins  = np.histogram(qdata, bins=inbins)\n",
    "\n",
    "    freq=np.array(n)/Npoints \n",
    "\n",
    "    # get the corners of the rectangles for the histogram\n",
    "\n",
    "    left = bins[:-1]\n",
    "    right = bins[1:]  \n",
    "    bottom = np.zeros(len(left))\n",
    "    top = bottom + freq\n",
    "    nrects = len(left)\n",
    "\n",
    "    # Here comes the tricky part -- we have to set up the vertex and path codes\n",
    "    # arrays using `.Path.MOVETO`, `.Path.LINETO` and `.Path.CLOSEPOLY` for each rect.\n",
    "\n",
    "    #* We need 1 ``MOVETO`` per rectangle, which sets the initial point.\n",
    "    #* We need 3 ``LINETO``'s, which tell Matplotlib to draw lines from\n",
    "    #  vertex 1 to vertex 2, v2 to v3, and v3 to v4.\n",
    "    #* We then need one ``CLOSEPOLY`` which tells Matplotlib to draw a line from\n",
    "    #  the v4 to our initial vertex (the ``MOVETO`` vertex), in order to close the\n",
    "    #  polygon.\n",
    "\n",
    "    #<div class=\"alert alert-info\"><h4>Note</h4><p>The vertex for ``CLOSEPOLY`` is ignored, but we still need a placeholder\n",
    "    #  in the ``verts`` array to keep the codes aligned with the vertices.</p></div>\n",
    "\n",
    "    nverts = nrects * (1 + 3 + 1)\n",
    "    verts = np.zeros((nverts, 2))\n",
    "    codes = np.full(nverts, path.Path.LINETO)\n",
    "    codes[0::5] = path.Path.MOVETO\n",
    "    codes[4::5] = path.Path.CLOSEPOLY\n",
    "    verts[0::5, 0] = left\n",
    "    verts[0::5, 1] = bottom\n",
    "    verts[1::5, 0] = left\n",
    "    verts[1::5, 1] = top\n",
    "    verts[2::5, 0] = right\n",
    "    verts[2::5, 1] = top\n",
    "    verts[3::5, 0] = right\n",
    "    verts[3::5, 1] = bottom\n",
    "\n",
    "    #patch = None\n",
    "\n",
    "    fig, ax = plt.subplots()\n",
    "    barpath = path.Path(verts, codes)\n",
    "    patch = patches.PathPatch(\n",
    "        barpath, facecolor='red', edgecolor='black', alpha=1)\n",
    "    ax.add_patch(patch)\n",
    "\n",
    "    if not type(pi) is int:\n",
    "        for m in range(len(pi)):\n",
    "            heightpi=pi[m]\n",
    "            widthpi=1\n",
    "            rectpi = Rectangle((m-1/2, 0), widthpi, heightpi, fc='white', ec ='black',lw = 2, alpha=0.5) \n",
    "            ax.add_patch(rectpi)\n",
    "    ax.set_xlim(-1/2, qmax+1/2) \n",
    "    ymax=max(freq)*1.5\n",
    "    ax.set_ylim(0, ymax)\n",
    "\n",
    "    plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Plot histogram of frequency of queue sizes in given data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "Qplot(qdata)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Add plot of equilibrium probabilities $\\pi$ (if known). As sample size increases the frequency equilibrium plots converge. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "Qplot(qdata,pi)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Q.1 (*) \n",
    "Simulate the Markov process with transition matrix: \n",
    "$$\n",
    "\\begin{bmatrix} \n",
    "1/2 & 0 & 1/2 & 0 & 0 & 0 \\\\ \n",
    "0 & 1/2 & 0 & 1/2 & 0 & 0 \\\\ \n",
    "0 & 0 & 1/2 & 0 & 1/2 & 0 \\\\ \n",
    "0 & 1/4 & 0 & 1/2 & 0 & 1/4 \\\\ \n",
    "1/4 & 0 & 1/4 & 0 & 1/2 & 0 \\\\ \n",
    "0 & 0 & 0 & 1/2 & 0 & 1/2%\n",
    "\\end{bmatrix}\n",
    "$$\n",
    "\n",
    "This is the same example as in Q.3 of Practical 1. Observe the long-time behaviour for initial queue size 0 and initial queue size 1. \n",
    "\n",
    "Observe what happens if the first row of the transition matrix is changed to $[1/4 , 1/4 , 1/2 , 0 , 0 , 0]$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "P=np.array([\n",
    "    [1/2,0,1/2,0,0,0],\n",
    "    [0,1/2,0,1/2,0,0],\n",
    "    [0,0,1/2,0,1/2,0],\n",
    "    [0,1/4,0,1/2,0,1/4],\n",
    "    [1/4,0,1/4,0,1/2,0],\n",
    "    [0,0,0,1/2,0,1/2]\n",
    "    ])\n",
    "print(P)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "qdata=Queue(P,0,1000)  # 1000 iterations with initial state 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(qdata)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "Qplot(qdata)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Q.2(*)\n",
    "A queue is observed 1000 time intervals with data as given in the array `qdata` below. \n",
    "This is the same as Question 4 of Practical 1.\n",
    "\n",
    "Compare the actual frequencies of events with a simulated one. Use the probabilities found in Practical 1. \n",
    "\n",
    "Look at that question again for examples of do loops and if else statements in Python"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "qdata = [4, 5, 6, 6, 6, 7, 6, 7, 6, 5, 4, 4, 5, 6, 7, 6, 5, 4, 3, 4, 5, 6, 5, 4, 3, 2, 1, 2, 3, 2, 1, \n",
    "         2, 3, 4, 3, 2, 3, 2, 1, 1, 2, 2, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 2, 3, 4, 5, 4, 5, 6, 7, \n",
    "         8, 7, 6, 7, 6, 6, 5, 4, 5, 4, 3, 2, 3, 2, 3, 2, 3, 2, 1, 1, 2, 3, 3, 4, 5, 6, 7, 6, 5, 6, 5, \n",
    "         6, 5, 6, 5, 4, 5, 4, 3, 4, 3, 4, 3, 2, 1, 0, 0, 0, 0, 1, 2, 1, 0, 1, 2, 3, 3, 2, 3, 4, 3, 2, \n",
    "         3, 2, 1, 2, 3, 2, 3, 2, 1, 0, 0, 1, 1, 2, 3, 2, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 2, 1, 2, \n",
    "         1, 2, 3, 4, 3, 4, 5, 6, 5, 6, 5, 6, 7, 7, 6, 5, 4, 3, 4, 3, 3, 4, 3, 2, 3, 2, 3, 2, 1, 2, 1, \n",
    "         2, 1, 0, 0, 0, 0, 1, 2, 3, 2, 2, 3, 2, 1, 0, 1, 2, 1, 0, 1, 0, 1, 0, 1, 2, 1, 0, 0, 1, 0, 1, \n",
    "         0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 2, 1, 1, 1, 0, 0, 1, 2, 3, 2, 3, 3, 4, 5, 6, 5, 4, 3, 2, 1, 2, \n",
    "         1, 0, 0, 0, 1, 2, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 1, 1, 2, \n",
    "         1, 0, 0, 1, 2, 3, 2, 3, 2, 2, 3, 4, 4, 5, 4, 3, 2, 3, 2, 3, 2, 3, 2, 1, 0, 1, 2, 3, 2, 1, 2, \n",
    "         1, 0, 1, 0, 1, 2, 3, 3, 2, 1, 1, 2, 1, 2, 1, 2, 1, 2, 3, 2, 2, 1, 0, 1, 2, 1, 2, 3, 4, 4, 3, \n",
    "         2, 2, 1, 2, 3, 4, 5, 4, 4, 5, 4, 3, 4, 3, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 2, \n",
    "         1, 2, 2, 3, 2, 3, 4, 5, 6, 5, 6, 5, 4, 5, 6, 7, 6, 5, 6, 6, 7, 6, 7, 7, 6, 7, 6, 5, 4, 5, 5, \n",
    "         4, 5, 6, 6, 5, 6, 5, 6, 5, 6, 5, 5, 5, 4, 3, 4, 5, 6, 5, 4, 3, 3, 4, 3, 2, 3, 2, 3, 3, 2, 1, \n",
    "         2, 1, 0, 0, 0, 0, 0, 1, 2, 3, 2, 3, 4, 5, 6, 7, 7, 8, 9, 8, 9, 8, 7, 6, 5, 5, 4, 5, 4, 3, 2, \n",
    "         1, 0, 1, 2, 1, 2, 3, 4, 5, 6, 7, 7, 8, 7, 8, 9, 8, 7, 6, 5, 4, 3, 4, 3, 4, 4, 5, 4, 3, 4, 3, \n",
    "         2, 3, 2, 3, 3, 2, 1, 1, 0, 1, 2, 1, 2, 2, 3, 4, 5, 6, 5, 4, 3, 2, 1, 0, 1, 0, 1, 0, 0, 1, 2, \n",
    "         3, 2, 1, 0, 0, 1, 2, 3, 4, 3, 2, 3, 2, 2, 1, 0, 1, 0, 0, 1, 0, 1, 2, 3, 4, 5, 6, 7, 6, 7, 7, \n",
    "         6, 7, 8, 8, 9, 10, 9, 10, 9, 10, 11, 10, 9, 8, 9, 10, 11, 10, 10, 9, 10, 10, 9, 8, 7, 8, 9, 10,\n",
    "         9, 8, 7, 6, 7, 6, 7, 6, 5, 4, 4, 5, 4, 3, 2, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 2, 1, 2, 1, 0, 0, \n",
    "         0, 0, 1, 0, 0, 1, 0, 1, 2, 3, 2, 3, 2, 3, 4, 3, 2, 1, 1, 2, 1, 2, 1, 2, 1, 2, 2, 1, 2, 3, 2, \n",
    "         2, 2, 1, 0, 1, 2, 3, 4, 5, 4, 5, 4, 3, 2, 3, 4, 5, 5, 4, 3, 4, 3, 4, 5, 4, 3, 2, 1, 0, 1, 2, \n",
    "         3, 4, 3, 2, 3, 4, 3, 2, 3, 2, 1, 0, 0, 0, 0, 0, 1, 0, 1, 2, 3, 4, 5, 4, 5, 4, 5, 6, 5, 4, 5, \n",
    "         6, 5, 4, 3, 2, 1, 0, 0, 1, 0, 0, 1, 0, 1, 2, 3, 4, 3, 4, 3, 2, 1, 1, 2, 3, 2, 3, 2, 3, 2, 3, \n",
    "         4, 3, 4, 4, 5, 6, 7, 6, 7, 7, 6, 5, 4, 3, 4, 3, 2, 2, 3, 4, 3, 4, 3, 2, 1, 0, 0, 1, 2, 3, 2, \n",
    "         1, 2, 3, 2, 1, 0, 0, 0, 0, 1, 1, 2, 3, 2, 3, 2, 3, 4, 5, 6, 5, 5, 4, 3, 4, 5, 4, 3, 4, 5, 4, \n",
    "         3, 2, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 2, 1, 0, 0, 0, 1, 0, 0, 1, 2, 3, 2, 3, 2, 3, 3, 4, \n",
    "         3, 2, 3, 2, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 2, 1, 2, 1, 0, 1, 2, 1, 2, 1, 2, 3, 2, 3, 2, 1, 0, \n",
    "         0, 0, 1, 2, 2, 3, 3, 2, 3, 4, 3, 2, 1, 2, 3, 3, 2, 1, 0, 1, 2, 2, 3, 4, 5, 6, 7, 7, 6, 5, 4, \n",
    "         5, 4, 5, 4, 3, 2, 3, 4, 3, 2, 1, 2, 3, 4, 3, 2, 3, 2, 1, 0, 1, 2, 1, 0, 0, 0, 0, 0, 0, 1, 0, \n",
    "         0, 1, 2, 2, 3, 2, 1, 0, 1, 2, 3, 4, 4, 3, 4, 3, 2, 1, 0, 0, 0, 0, 1, 0, 1, 1, 0, 1, 2, 2, 1, \n",
    "         0, 0, 1, 0, 1, 2, 2, 3, 3, 4, 3, 2, 3, 2, 1, 0, 0, 1, 2, 1, 2, 3, 2, 1, 2, 3, 2, 3, 2, 1, 0, \n",
    "         1, 2, 1, 2, 3, 2, 3, 2, 1, 1, 0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Q.3(*)\n",
    "A queue is observed 10000 time intervals with data as given in the array `qdata` below. \n",
    "This is the same as Question 5 of Practical 1.\n",
    "\n",
    "(a) Construct a simple model for this queue as a Markov chain with only nearest neighbour interactions.\n",
    " 1. Estimate the transition probabilities.\n",
    " 2. What is the expected behaviour of the queue as time continues?\n",
    " 3. Is the system ergodic ?\n",
    "\n",
    "(b) Suppose that the time step used is known to be 10 sec.\n",
    " 1. What is the average waiting time for customer service/arrival?\n",
    " 2. What is average number of servicings/arrivals per minute?\n",
    "\n",
    "(c) Simulate this system and compare the actual frequencies of events with the simulated ones.\n",
    "  \n",
    "  \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "qdata = [5, 5, 5, 6, 5, 6, 6, 7, 6, 5, 6, 5, 4, 5, 6, 6, 6, 7, 8, 7, 6, 6, 6, 5, 4, 4, 5, 5, 4, 5, 6, 6, 5, 4, 3, 3, 2, 2, 1, 2, 2, 3, 3, 2, 3, 4, 3, 2, 3, 3, 4, 4, 3, 4, 3, 3, 4, 3, 3, 3, 4, 4, 5, 5, 5, 6, 6, 7, 6, 7, 6, 5, 4, 4, 3, 3, 2, 1, 1, 2, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 2, 1, 2, 1, 0, 0, 1, 1, 0, 1, 1, 0, 1, 1, 2, 3, 4, 4, 3, 2, 2, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 2, 3, 3, 2, 1, 2, 1, 2, 1, 2, 3, 4, 5, 5, 6, 5, 6, 5, 4, 4, 4, 3, 2, 2, 1, 2, 2, 3, 2, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 2, 2, 2, 1, 2, 1, 1, 0, 1, 2, 1, 0, 0, 1, 1, 0, 1, 1, 2, 3, 4, 3, 2, 1, 2, 3, 3, 2, 1, 0, 0, 0, 0, 1, 2, 1, 0, 1, 2, 1, 1, 1, 1, 2, 3, 4, 5, 6, 6, 7, 6, 5, 4, 5, 5, 4, 3, 2, 1, 0, 0, 1, 0, 1, 1, 2, 2, 3, 2, 1, 2, 3, 2, 3, 4, 4, 4, 5, 6, 7, 6, 5, 4, 3, 3, 2, 3, 3, 2, 1, 2, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 2, 1, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 2, 2, 2, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 1, 2, 2, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 2, 1, 0, 0, 1, 1, 2, 2, 3, 2, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 1, 1, 2, 2, 3, 2, 1, 2, 1, 1, 1, 2, 3, 4, 4, 3, 3, 2, 1, 2, 3, 4, 5, 4, 5, 6, 5, 4, 4, 4, 4, 3, 2, 1, 1, 2, 2, 1, 1, 0, 1, 1, 2, 3, 2, 2, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 2, 2, 2, 2, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 2, 2, 2, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 0, 0, 1, 2, 1, 1, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 1, 2, 1, 1, 0, 0, 1, 1, 1, 1, 1, 2, 3, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 1, 1, 0, 1, 2, 2, 2, 2, 3, 2, 1, 1, 1, 1, 0, 0, 1, 0, 1, 2, 2, 1, 2, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 2, 2, 3, 3, 2, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0, 1, 0, 1, 2, 3, 2, 3, 3, 2, 3, 2, 3, 2, 3, 3, 3, 3, 4, 4, 4, 4, 3, 4, 4, 4, 5, 4, 5, 5, 5, 4, 3, 4, 4, 5, 6, 7, 6, 6, 7, 7, 6, 7, 7, 7, 7, 8, 8, 7, 7, 8, 9, 10, 11, 10, 11, 10, 9, 8, 8, 7, 8, 9, 8, 8, 7, 7, 6, 6, 6, 5, 5, 5, 5, 5, 5, 5, 6, 5, 5, 6, 7, 8, 7, 7, 6, 5, 4, 4, 3, 3, 4, 5, 5, 4, 3, 2, 3, 4, 4, 4, 4, 4, 3, 3, 4, 5, 5, 6, 6, 6, 6, 6, 5, 5, 4, 4, 3, 2, 2, 1, 0, 1, 2, 2, 3, 2, 3, 3, 2, 1, 2, 3, 2, 1, 2, 2, 3, 4, 4, 4, 5, 6, 5, 6, 7, 6, 6, 5, 4, 3, 3, 4, 4, 5, 4, 4, 5, 4, 3, 2, 2, 1, 0, 1, 2, 2, 1, 2, 2, 2, 2, 2, 1, 2, 2, 2, 3, 4, 5, 4, 3, 3, 2, 3, 3, 3, 4, 3, 4, 5, 6, 7, 8, 9, 10, 10, 11, 12, 12, 11, 11, 10, 11, 11, 11, 10, 9, 9, 10, 10, 9, 8, 8, 7, 7, 6, 7, 8, 8, 8, 8, 7, 8, 7, 7, 6, 5, 6, 6, 6, 7, 8, 7, 7, 6, 6, 5, 5, 6, 7, 7, 7, 6, 7, 8, 9, 8, 7, 7, 6, 6, 6, 7, 8, 9, 9, 10, 11, 11, 12, 12, 13, 14, 14, 15, 16, 15, 15, 16, 15, 14, 13, 14, 15, 14, 13, 14, 15, 15, 14, 14, 13, 14, 14, 15, 14, 15, 14, 13, 12, 12, 11, 12, 12, 13, 13, 14, 14, 15, 15, 15, 16, 17, 18, 17, 17, 18, 19, 19, 18, 17, 16, 17, 18, 18, 18, 17, 18, 17, 16, 15, 14, 13, 12, 12, 13, 12, 12, 12, 11, 11, 10, 11, 12, 11, 12, 11, 11, 10, 10, 10, 9, 8, 9, 10, 9, 9, 8, 8, 9, 8, 8, 8, 7, 7, 8, 9, 10, 10, 11, 10, 11, 12, 12, 11, 10, 10, 11, 11, 11, 10, 11, 11, 10, 9, 10, 11, 10, 11, 12, 12, 11, 10, 9, 8, 8, 9, 8, 7, 8, 8, 8, 9, 9, 10, 11, 11, 12, 11, 10, 10, 9, 8, 9, 10, 11, 12, 12, 13, 12, 13, 12, 11, 10, 11, 10, 11, 10, 9, 8, 8, 7, 6, 7, 6, 6, 7, 8, 8, 7, 6, 7, 6, 6, 5, 4, 4, 3, 2, 3, 4, 3, 4, 4, 3, 4, 3, 3, 2, 2, 2, 2, 2, 3, 2, 1, 1, 2, 2, 2, 1, 0, 0, 0, 0, 1, 1, 2, 1, 0, 0, 1, 2, 2, 1, 2, 1, 2, 2, 2, 1, 2, 1, 1, 2, 1, 2, 1, 2, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 2, 3, 4, 4, 5, 5, 4, 4, 3, 3, 2, 1, 2, 1, 1, 2, 3, 2, 1, 2, 2, 1, 2, 1, 0, 1, 2, 3, 2, 3, 4, 4, 3, 4, 3, 3, 2, 2, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 2, 2, 3, 3, 4, 3, 3, 2, 1, 1, 2, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 1, 2, 2, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 2, 1, 2, 3, 3, 2, 2, 3, 4, 5, 5, 5, 5, 4, 5, 4, 5, 4, 4, 4, 3, 4, 3, 4, 5, 4, 5, 4, 3, 2, 3, 2, 3, 4, 3, 4, 5, 6, 6, 5, 5, 5, 6, 5, 6, 6, 7, 7, 8, 9, 10, 9, 10, 11, 12, 12, 13, 13, 13, 12, 12, 12, 11, 11, 10, 10, 9, 8, 7, 6, 6, 7, 7, 8, 8, 9, 10, 9, 8, 9, 10, 10, 10, 10, 10, 11, 11, 11, 11, 12, 13, 13, 12, 12, 11, 12, 11, 10, 9, 8, 7, 7, 8, 7, 8, 7, 7, 7, 6, 6, 6, 6, 5, 6, 5, 6, 5, 6, 7, 6, 5, 6, 5, 5, 4, 5, 5, 6, 6, 7, 6, 5, 4, 4, 3, 2, 3, 2, 1, 0, 0, 0, 1, 0, 1, 2, 2, 2, 2, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 2, 1, 0, 0, 0, 1, 2, 3, 2, 2, 1, 0, 0, 0, 0, 1, 1, 2, 1, 0, 1, 1, 2, 3, 3, 3, 2, 2, 3, 4, 5, 5, 4, 4, 5, 5, 6, 5, 5, 6, 5, 4, 5, 4, 5, 6, 5, 5, 4, 5, 5, 6, 7, 7, 7, 8, 9, 9, 8, 7, 6, 5, 4, 5, 4, 5, 4, 5, 5, 4, 3, 4, 5, 4, 4, 3, 3, 2, 1, 1, 2, 2, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 1, 2, 2, 2, 3, 2, 2, 3, 3, 3, 2, 1, 2, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 2, 3, 4, 5, 4, 3, 3, 4, 3, 2, 2, 1, 0, 1, 1, 1, 2, 1, 1, 2, 1, 1, 2, 2, 2, 2, 3, 3, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 1, 2, 3, 4, 5, 5, 4, 3, 4, 4, 4, 4, 3, 3, 4, 5, 4, 5, 5, 4, 5, 6, 5, 6, 5, 5, 6, 6, 5, 6, 6, 7, 6, 5, 5, 5, 4, 5, 4, 3, 3, 3, 3, 4, 3, 4, 5, 4, 3, 4, 3, 2, 2, 1, 1, 2, 3, 2, 3, 3, 4, 4, 5, 4, 5, 6, 6, 7, 8, 7, 7, 7, 8, 9, 9, 8, 9, 8, 9, 8, 7, 7, 6, 6, 7, 8, 9, 9, 10, 9, 8, 7, 7, 6, 5, 5, 4, 3, 3, 4, 5, 6, 6, 7, 7, 8, 9, 9, 10, 10, 10, 11, 12, 13, 14, 15, 14, 15, 14, 13, 13, 13, 14, 15, 15, 14, 13, 13, 13, 12, 12, 12, 13, 12, 12, 13, 12, 11, 12, 11, 10, 10, 9, 8, 8, 9, 9, 10, 11, 11, 10, 10, 9, 9, 9, 9, 10, 10, 9, 10, 11, 10, 11, 11, 11, 10, 10, 11, 12, 11, 12, 13, 12, 11, 12, 11, 10, 10, 9, 9, 10, 11, 10, 11, 10, 10, 9, 9, 9, 9, 8, 9, 8, 9, 10, 10, 9, 8, 7, 8, 7, 6, 5, 6, 5, 4, 5, 5, 6, 5, 4, 5, 5, 4, 3, 4, 3, 2, 1, 2, 3, 3, 3, 2, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 2, 3, 2, 3, 4, 3, 2, 2, 2, 2, 2, 1, 2, 1, 0, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 2, 2, 3, 3, 4, 3, 2, 2, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 1, 2, 3, 3, 3, 4, 4, 4, 3, 3, 2, 3, 2, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 2, 1, 2, 2, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 2, 1, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 2, 3, 3, 3, 3, 3, 2, 3, 4, 3, 2, 2, 3, 3, 2, 2, 2, 1, 2, 1, 2, 2, 1, 0, 0, 0, 0, 0, 0, 1, 2, 1, 0, 1, 2, 3, 2, 2, 1, 2, 1, 0, 0, 0, 1, 2, 1, 0, 0, 1, 2, 2, 2, 2, 1, 0, 0, 0, 0, 1, 2, 3, 2, 3, 2, 3, 4, 3, 4, 4, 4, 4, 5, 5, 4, 5, 4, 5, 6, 7, 8, 8, 7, 6, 7, 7, 8, 8, 7, 6, 7, 7, 7, 6, 6, 7, 7, 8, 9, 8, 7, 6, 7, 7, 8, 8, 7, 8, 9, 10, 9, 10, 11, 12, 11, 11, 12, 11, 10, 10, 10, 10, 11, 10, 11, 12, 12, 12, 12, 12, 12, 11, 12, 11, 11, 10, 9, 9, 8, 8, 7, 6, 7, 7, 6, 7, 6, 7, 6, 5, 6, 7, 7, 7, 8, 8, 9, 8, 7, 6, 5, 4, 5, 6, 7, 7, 6, 7, 8, 7, 8, 8, 8, 7, 8, 7, 6, 6, 5, 5, 6, 6, 5, 6, 7, 6, 7, 6, 6, 5, 5, 6, 5, 6, 6, 7, 7, 6, 7, 7, 8, 9, 9, 8, 7, 8, 7, 6, 7, 8, 9, 10, 11, 10, 9, 9, 9, 8, 9, 8, 7, 6, 6, 7, 6, 5, 4, 3, 2, 3, 4, 3, 2, 2, 2, 3, 4, 3, 3, 4, 3, 2, 3, 4, 4, 4, 3, 2, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 2, 3, 2, 3, 3, 2, 3, 3, 2, 2, 3, 2, 3, 2, 1, 2, 3, 2, 2, 1, 2, 2, 3, 2, 2, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 2, 1, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 2, 2, 2, 3, 2, 2, 1, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 2, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 2, 3, 3, 2, 2, 1, 1, 0, 0, 1, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1, 1, 2, 1, 1, 1, 2, 3, 2, 3, 3, 2, 1, 0, 0, 0, 0, 0, 1, 2, 3, 2, 2, 3, 2, 1, 0, 1, 1, 2, 3, 2, 2, 3, 3, 3, 3, 3, 4, 3, 2, 3, 2, 2, 3, 3, 2, 1, 2, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 2, 2, 2, 2, 3, 2, 1, 1, 1, 1, 2, 3, 4, 4, 4, 4, 5, 6, 5, 4, 4, 3, 3, 2, 1, 1, 2, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 2, 1, 0, 0, 0, 0, 0, 1, 2, 2, 1, 0, 0, 1, 0, 0, 0, 1, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 3, 3, 2, 1, 0, 0, 0, 1, 0, 1, 2, 3, 4, 4, 4, 5, 4, 4, 5, 4, 5, 6, 5, 5, 6, 7, 7, 7, 7, 6, 7, 6, 6, 5, 4, 3, 3, 4, 3, 3, 3, 4, 3, 3, 4, 3, 2, 3, 2, 1, 1, 2, 1, 2, 1, 1, 2, 1, 1, 2, 2, 1, 2, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 1, 2, 2, 3, 3, 4, 5, 4, 3, 3, 3, 2, 1, 1, 2, 2, 2, 2, 3, 2, 2, 2, 1, 2, 3, 4, 4, 3, 2, 3, 2, 3, 4, 4, 3, 3, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 2, 2, 2, 2, 1, 1, 1, 1, 0, 0, 1, 2, 3, 4, 5, 4, 5, 5, 4, 5, 4, 3, 2, 1, 2, 1, 2, 3, 2, 3, 4, 4, 5, 4, 5, 6, 6, 7, 8, 8, 9, 9, 10, 11, 12, 11, 10, 11, 10, 9, 8, 7, 6, 5, 6, 6, 7, 6, 6, 5, 4, 3, 2, 2, 1, 0, 0, 0, 1, 0, 1, 2, 3, 4, 5, 5, 5, 4, 3, 2, 2, 3, 3, 2, 1, 1, 2, 2, 1, 1, 2, 2, 1, 2, 1, 1, 2, 3, 2, 2, 2, 3, 3, 3, 4, 3, 2, 2, 2, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 1, 2, 3, 3, 4, 5, 6, 5, 5, 5, 4, 5, 4, 5, 4, 5, 4, 3, 3, 3, 2, 1, 1, 2, 2, 3, 4, 5, 6, 7, 7, 6, 7, 6, 7, 8, 8, 9, 10, 11, 12, 13, 14, 14, 14, 15, 16, 16, 15, 15, 16, 17, 18, 17, 16, 15, 15, 14, 15, 14, 13, 14, 15, 14, 13, 13, 12, 12, 13, 12, 13, 13, 13, 13, 12, 13, 14, 13, 13, 13, 13, 13, 12, 11, 11, 10, 9, 9, 10, 9, 10, 9, 9, 10, 9, 9, 10, 10, 11, 10, 9, 9, 10, 10, 10, 10, 10, 9, 8, 8, 7, 7, 8, 7, 8, 8, 7, 7, 7, 8, 7, 7, 7, 6, 5, 4, 3, 4, 5, 5, 4, 3, 2, 1, 1, 1, 2, 3, 2, 2, 3, 2, 3, 2, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 1, 1, 2, 2, 2, 1, 1, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 2, 1, 0, 0, 0, 1, 2, 2, 2, 2, 3, 2, 1, 0, 0, 0, 0, 1, 2, 1, 2, 2, 2, 3, 4, 5, 6, 5, 6, 5, 4, 5, 6, 6, 5, 5, 5, 4, 5, 4, 4, 4, 3, 4, 3, 2, 1, 0, 0, 1, 2, 3, 4, 4, 4, 5, 5, 5, 5, 4, 5, 4, 5, 6, 7, 6, 5, 5, 6, 5, 6, 5, 5, 6, 7, 7, 7, 8, 9, 9, 10, 10, 9, 9, 8, 7, 8, 9, 10, 9, 9, 9, 9, 10, 10, 10, 9, 8, 8, 9, 8, 7, 8, 9, 9, 10, 10, 11, 12, 11, 10, 11, 10, 9, 9, 10, 10, 10, 10, 10, 10, 10, 9, 9, 8, 9, 9, 10, 11, 12, 12, 12, 12, 12, 13, 12, 12, 11, 10, 9, 10, 10, 10, 9, 10, 9, 9, 9, 9, 8, 7, 6, 7, 7, 6, 6, 7, 8, 9, 8, 8, 9, 9, 10, 9, 10, 9, 8, 8, 8, 9, 10, 11, 10, 11, 12, 13, 14, 14, 14, 13, 13, 12, 12, 11, 12, 13, 14, 13, 13, 12, 13, 13, 12, 12, 12, 13, 13, 13, 13, 12, 13, 12, 13, 14, 15, 15, 15, 16, 16, 16, 16, 16, 16, 16, 15, 15, 16, 15, 16, 15, 15, 16, 15, 14, 15, 14, 14, 13, 12, 13, 14, 15, 16, 16, 16, 16, 15, 15, 14, 14, 15, 15, 16, 16, 16, 16, 17, 18, 19, 19, 18, 19, 18, 19, 20, 19, 18, 19, 20, 20, 19, 19, 19, 20, 20, 19, 18, 18, 19, 18, 17, 16, 15, 15, 15, 14, 14, 14, 14, 14, 14, 13, 12, 12, 13, 13, 14, 15, 15, 16, 17, 18, 18, 17, 18, 17, 17, 17, 16, 15, 14, 14, 15, 14, 13, 14, 14, 15, 16, 17, 16, 17, 18, 19, 18, 19, 19, 20, 19, 18, 19, 18, 18, 17, 17, 18, 19, 20, 19, 18, 19, 20, 19, 20, 20, 20, 20, 19, 18, 19, 19, 19, 18, 18, 18, 18, 19, 18, 17, 16, 15, 14, 15, 16, 15, 14, 14, 14, 13, 12, 11, 10, 11, 10, 9, 10, 9, 9, 8, 8, 7, 7, 7, 6, 5, 6, 7, 7, 8, 7, 8, 8, 9, 10, 11, 10, 11, 12, 11, 10, 10, 9, 8, 7, 8, 8, 7, 7, 7, 8, 8, 8, 7, 8, 7, 7, 6, 6, 7, 8, 8, 8, 7, 8, 7, 8, 7, 6, 6, 7, 6, 6, 5, 4, 5, 6, 7, 7, 8, 7, 6, 5, 4, 3, 4, 3, 2, 3, 2, 3, 2, 1, 0, 0, 1, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 2, 1, 0, 0, 0, 1, 2, 3, 4, 3, 2, 2, 2, 2, 3, 4, 5, 5, 6, 5, 6, 5, 6, 5, 5, 6, 6, 5, 4, 4, 4, 4, 3, 3, 2, 2, 2, 1, 0, 0, 0, 1, 2, 3, 3, 2, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 2, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 2, 3, 4, 3, 2, 1, 2, 2, 1, 2, 2, 3, 4, 3, 4, 3, 2, 1, 1, 0, 1, 2, 3, 4, 4, 3, 4, 5, 6, 6, 6, 5, 5, 6, 5, 4, 3, 2, 2, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 1, 2, 1, 1, 2, 3, 3, 2, 3, 3, 3, 4, 3, 3, 2, 2, 1, 0, 1, 2, 2, 1, 0, 0, 0, 0, 1, 0, 0, 1, 1, 2, 1, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 2, 1, 1, 1, 1, 2, 1, 1, 2, 2, 2, 3, 4, 3, 4, 4, 5, 6, 5, 4, 3, 2, 2, 1, 1, 1, 2, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 1, 0, 0, 0, 1, 1, 2, 3, 4, 4, 3, 4, 4, 3, 4, 3, 4, 3, 3, 2, 1, 2, 1, 0, 0, 0, 0, 0, 0, 1, 2, 1, 0, 0, 0, 1, 0, 1, 1, 1, 1, 2, 2, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 1, 1, 2, 1, 2, 2, 2, 3, 2, 3, 2, 1, 2, 1, 1, 1, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 2, 1, 1, 2, 2, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 2, 3, 2, 2, 1, 2, 2, 3, 2, 2, 2, 2, 1, 0, 0, 0, 0, 0, 0, 0, 1, 2, 3, 4, 5, 5, 6, 6, 7, 6, 5, 5, 5, 6, 5, 4, 4, 3, 2, 3, 2, 1, 0, 0, 1, 2, 1, 2, 1, 1, 1, 1, 2, 3, 4, 4, 3, 3, 4, 3, 4, 3, 4, 4, 3, 2, 3, 3, 4, 4, 3, 2, 3, 3, 2, 2, 1, 2, 2, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 1, 0, 1, 1, 2, 2, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 1, 2, 2, 1, 2, 1, 0, 0, 0, 0, 1, 0, 1, 2, 3, 2, 3, 4, 5, 5, 6, 6, 6, 5, 6, 5, 5, 5, 4, 3, 4, 3, 2, 2, 3, 4, 3, 2, 1, 2, 3, 2, 1, 2, 1, 1, 1, 0, 0, 0, 1, 2, 1, 2, 3, 2, 2, 1, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 2, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 2, 2, 1, 1, 1, 0, 1, 2, 2, 3, 3, 4, 3, 4, 4, 3, 4, 3, 4, 3, 4, 5, 5, 4, 3, 4, 3, 3, 3, 3, 3, 4, 4, 3, 4, 3, 3, 3, 2, 1, 2, 3, 2, 1, 2, 2, 3, 4, 5, 5, 6, 7, 7, 6, 6, 5, 4, 3, 4, 4, 4, 5, 4, 3, 2, 1, 2, 2, 3, 2, 1, 0, 0, 0, 1, 2, 1, 1, 2, 3, 3, 2, 2, 3, 2, 1, 2, 3, 4, 4, 3, 4, 4, 4, 3, 3, 2, 1, 2, 1, 2, 3, 4, 5, 5, 5, 6, 6, 7, 8, 8, 8, 9, 8, 9, 8, 7, 8, 7, 7, 6, 6, 6, 7, 6, 6, 5, 4, 5, 5, 5, 6, 6, 6, 6, 7, 6, 5, 6, 5, 6, 6, 6, 5, 5, 5, 4, 3, 3, 2, 3, 2, 1, 0, 0, 0, 0, 0, 1, 2, 1, 0, 0, 0, 1, 2, 1, 2, 2, 1, 0, 1, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 2, 2, 2, 1, 1, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 1, 1, 1, 1, 2, 1, 1, 2, 3, 2, 3, 3, 4, 4, 5, 4, 3, 2, 1, 2, 1, 2, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 2, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 2, 1, 1, 2, 2, 3, 2, 2, 3, 4, 4, 4, 3, 3, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 1, 2, 1, 2, 1, 1, 0, 0, 0, 0, 1, 0, 1, 2, 2, 1, 1, 0, 0, 1, 1, 0, 1, 1, 2, 3, 4, 5, 6, 6, 5, 4, 4, 3, 3, 2, 3, 2, 2, 2, 2, 2, 2, 1, 0, 1, 0, 0, 0, 0, 1, 1, 1, 2, 1, 1, 2, 2, 1, 2, 2, 3, 2, 3, 4, 4, 5, 5, 4, 5, 6, 5, 5, 5, 5, 6, 5, 5, 6, 6, 7, 8, 8, 9, 8, 9, 9, 8, 7, 7, 6, 6, 5, 4, 4, 3, 3, 2, 2, 1, 1, 0, 0, 1, 0, 1, 2, 2, 1, 1, 2, 2, 1, 1, 2, 3, 4, 3, 3, 2, 2, 3, 4, 4, 3, 2, 3, 4, 4, 3, 4, 5, 5, 5, 5, 4, 3, 3, 4, 3, 3, 4, 5, 4, 4, 3, 4, 3, 4, 3, 4, 5, 5, 4, 5, 6, 7, 6, 5, 4, 5, 6, 5, 4, 4, 4, 4, 5, 4, 3, 4, 3, 2, 1, 0, 0, 0, 1, 1, 2, 1, 2, 2, 2, 3, 3, 4, 5, 5, 5, 6, 5, 4, 3, 2, 3, 3, 4, 3, 3, 2, 2, 1, 2, 2, 1, 2, 3, 3, 3, 3, 4, 5, 5, 4, 5, 5, 4, 3, 3, 2, 2, 1, 2, 1, 2, 3, 4, 4, 4, 5, 4, 4, 4, 3, 3, 4, 4, 3, 4, 4, 5, 6, 5, 5, 6, 7, 7, 7, 7, 6, 6, 5, 4, 4, 3, 3, 2, 3, 2, 1, 1, 2, 3, 2, 1, 1, 1, 1, 2, 2, 2, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 3, 3, 4, 3, 3, 4, 5, 5, 6, 6, 7, 6, 6, 7, 7, 6, 5, 6, 7, 8, 8, 9, 9, 9, 10, 9, 8, 7, 7, 7, 7, 6, 5, 4, 4, 5, 4, 4, 3, 2, 1, 2, 3, 2, 1, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 2, 1, 2, 2, 2, 1, 2, 1, 1, 1, 1, 0, 0, 1, 2, 1, 2, 2, 2, 2, 2, 3, 2, 3, 4, 3, 4, 5, 4, 4, 5, 6, 6, 7, 7, 6, 7, 6, 6, 5, 5, 6, 6, 7, 6, 5, 5, 4, 5, 5, 4, 3, 2, 2, 2, 2, 3, 3, 3, 2, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 2, 2, 2, 3, 4, 4, 5, 4, 4, 5, 5, 4, 4, 5, 4, 4, 3, 2, 1, 0, 0, 1, 0, 0, 1, 1, 2, 2, 2, 3, 2, 3, 3, 2, 1, 2, 3, 3, 3, 3, 2, 2, 2, 3, 4, 3, 3, 4, 5, 6, 7, 6, 6, 7, 6, 5, 4, 3, 4, 3, 2, 3, 3, 3, 2, 3, 2, 2, 2, 1, 0, 1, 1, 2, 2, 1, 2, 3, 2, 2, 1, 0, 0, 0, 1, 2, 3, 3, 2, 2, 2, 3, 4, 5, 5, 4, 5, 4, 3, 4, 5, 4, 3, 3, 4, 3, 2, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 1, 0, 0, 0, 1, 0, 0, 1, 2, 3, 3, 3, 2, 2, 3, 4, 3, 2, 2, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 2, 3, 4, 5, 4, 4, 5, 4, 3, 2, 3, 3, 4, 3, 2, 1, 1, 1, 2, 3, 4, 5, 5, 5, 6, 5, 5, 4, 5, 4, 5, 5, 4, 4, 4, 5, 5, 4, 3, 3, 4, 5, 5, 4, 4, 4, 3, 2, 3, 3, 3, 2, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 2, 3, 2, 1, 0, 1, 1, 2, 3, 4, 3, 4, 4, 3, 2, 1, 0, 0, 0, 1, 0, 1, 2, 1, 2, 2, 3, 2, 1, 1, 2, 1, 2, 3, 4, 4, 5, 6, 5, 5, 5, 4, 3, 2, 1, 2, 3, 2, 2, 2, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 2, 1, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 2, 1, 1, 2, 3, 2, 2, 1, 1, 2, 1, 2, 1, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 1, 2, 1, 0, 0, 1, 1, 2, 1, 2, 1, 2, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 2, 1, 0, 1, 1, 2, 3, 4, 3, 3, 2, 3, 2, 3, 3, 3, 2, 1, 0, 0, 0, 1, 2, 1, 2, 3, 2, 3, 3, 4, 4, 5, 6, 7, 7, 7, 7, 7, 8, 7, 8, 7, 7, 6, 7, 6, 5, 6, 5, 5, 4, 4, 4, 3, 2, 2, 3, 3, 2, 3, 2, 2, 3, 4, 4, 4, 5, 6, 7, 7, 6, 6, 5, 4, 5, 4, 3, 4, 4, 5, 6, 6, 6, 7, 7, 7, 6, 5, 6, 6, 7, 7, 8, 7, 8, 8, 9, 10, 10, 10, 9, 9, 9, 8, 7, 7, 6, 7, 6, 5, 6, 7, 7, 7, 8, 9, 10, 10, 11, 11, 12, 11, 11, 12, 11, 11, 10, 11, 12, 11, 10, 10, 11, 10, 10, 9, 8, 8, 7, 8, 9, 10, 9, 8, 9, 8, 8, 9, 9, 10, 10, 11, 10, 10, 11, 10, 10, 9, 8, 8, 9, 10, 11, 11, 12, 12, 13, 14, 14, 13, 12, 11, 12, 13, 14, 13, 12, 11, 10, 11, 10, 10, 10, 11, 11, 11, 10, 11, 10, 9, 9, 8, 9, 9, 10, 11, 12, 13, 12, 11, 12, 13, 13, 13, 12, 12, 12, 11, 12, 12, 11, 10, 9, 9, 9, 9, 9, 10, 9, 9, 9, 10, 11, 11, 12, 11, 10, 11, 10, 11, 11, 10, 9, 8, 7, 7, 8, 8, 7, 7, 6, 5, 6, 7, 8, 8, 8, 9, 8, 7, 6, 7, 6, 7, 7, 6, 5, 5, 6, 7, 8, 7, 6, 5, 5, 6, 7, 6, 7, 7, 8, 7, 6, 5, 4, 3, 2, 1, 2, 3, 4, 3, 2, 3, 4, 3, 2, 2, 2, 1, 1, 2, 3, 4, 4, 5, 4, 4, 3, 2, 2, 3, 2, 1, 0, 1, 1, 2, 1, 0, 0, 0, 0, 0, 1, 2, 1, 0, 1, 2, 1, 0, 1, 1, 2, 2, 3, 2, 3, 2, 1, 2, 3, 4, 4, 5, 6, 7, 7, 6, 6, 7, 6, 7, 8, 8, 8, 8, 9, 8, 8, 9, 9, 9, 10, 9, 9, 8, 9, 9, 10, 9, 9, 10, 9, 10, 9, 8, 8, 9, 9, 10, 9, 10, 9, 8, 9, 9, 8, 8, 9, 9, 9, 8, 7, 6, 5, 4, 4, 3, 4, 4, 3, 2, 3, 2, 3, 3, 2, 3, 2, 3, 4, 5, 5, 4, 3, 2, 1, 0, 0, 1, 2, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 2, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 2, 3, 4, 4, 5, 4, 4, 4, 3, 4, 5, 5, 4, 3, 2, 3, 2, 2, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 1, 2, 3, 3, 2, 2, 3, 3, 2, 1, 0, 0, 1, 2, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 2, 2, 1, 2, 3, 3, 3, 2, 3, 2, 3, 3, 3, 4, 3, 3, 3, 3, 4, 4, 5, 4, 4, 3, 3, 3, 3, 2, 3, 3, 3, 4, 3, 4, 5, 4, 5, 6, 5, 6, 6, 6, 6, 6, 7, 6, 7, 6, 5, 5, 5, 4, 4, 5, 5, 4, 3, 3, 4, 4, 5, 4, 3, 3, 2, 1, 1, 1, 2, 3, 4, 5, 4, 4, 4, 3, 3, 4, 4, 4, 3, 3, 4, 3, 4, 5, 4, 4, 3, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 2, 1, 0, 1, 2, 2, 2, 2, 1, 0, 0, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 2, 1, 1, 0, 0, 1, 1, 0, 0, 1, 2, 3, 4, 3, 2, 3, 4, 3, 4, 3, 3, 4, 5, 4, 5, 4, 5, 4, 3, 3, 3, 2, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 2, 2, 3, 4, 5, 4, 4, 3, 4, 4, 3, 4, 5, 6, 6, 6, 5, 5, 4, 3, 3, 3, 4, 4, 3, 2, 1, 0, 1, 2, 1, 0, 1, 2, 1, 1, 0, 0, 0, 1, 0, 0, 1, 2, 1, 2, 1, 1, 0, 0, 1, 2, 1, 1, 0, 0, 1, 0, 0, 1, 1, 2, 3, 3, 3, 2, 1, 2, 1, 2, 1, 0, 1, 2, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 2, 2, 3, 4, 4, 3, 3, 3, 3, 4, 4, 5, 6, 5, 4, 3, 3, 3, 3, 2, 2, 1, 1, 2, 1, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 2, 2, 2, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 2, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 2, 2, 2, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 2, 2, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 2, 2, 2, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 1, 1, 1, 2, 1, 0, 0, 0, 1, 0, 1, 2, 3, 4, 5, 6, 7, 6, 7, 8, 7, 6, 7, 8, 9, 8, 9, 10, 9, 8, 7, 6, 7, 7, 6, 7, 6, 5, 4, 3, 3, 2, 3, 4, 3, 3, 3, 3, 4, 3, 4, 5, 4, 5, 4, 3, 2, 3, 3, 2, 2, 3, 4, 4, 3, 2, 1, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 1, 1, 1, 2, 2, 3, 4, 5, 4, 3, 2, 2, 3, 3, 4, 3, 4, 4, 3, 3, 4, 3, 3, 2, 1, 0, 1, 0, 1, 1, 2, 1, 0, 0, 0, 0, 0, 0, 1, 2, 3, 3, 2, 2, 2, 2, 1, 1, 2, 1, 1, 1, 0, 1, 2, 2, 1, 2, 1, 1, 2, 1, 2, 2, 3, 4, 3, 2, 3, 3, 3, 3, 4, 5, 4, 3, 2, 1, 1, 0, 1, 0, 1, 1, 2, 2, 3, 3, 3, 2, 3, 2, 1, 2, 1, 1, 1, 0, 0, 0, 0, 1, 2, 3, 3, 2, 3, 2, 2, 2, 1, 1, 2, 1, 0, 0, 0, 0, 1, 1, 2, 3, 3, 3, 4, 3, 3, 2, 2, 3, 2, 3, 4, 3, 2, 3, 2, 1, 1, 2, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 2, 1, 1, 1, 2, 3, 4, 5, 4, 4, 3, 3, 3, 4, 4, 3, 4, 4, 3, 2, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 2, 2, 2, 3, 4, 3, 4, 3, 2, 1, 2, 3, 2, 1, 2, 2, 1, 1, 1, 0, 1, 2, 3, 4, 5, 5, 6, 7, 6, 5, 5, 4, 5, 4, 4, 3, 2, 3, 3, 2, 2, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 2, 2, 1, 0, 0, 1, 1, 0, 0, 1, 2, 3, 2, 2, 2, 2, 2, 2, 2, 3, 2, 2, 1, 1, 1, 2, 3, 3, 3, 2, 2, 2, 1, 2, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 2, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 2, 1, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 2, 2, 2, 1, 2, 3, 3, 2, 3, 3, 2, 3, 2, 1, 0, 1, 2, 3, 2, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 2, 3, 3, 4, 3, 4, 3, 2, 2, 2, 1, 2, 2, 2, 1, 2, 3, 2, 3, 2, 3, 3, 4, 5, 6, 6, 5, 6, 7, 8, 8, 7, 6, 5, 4, 3, 3, 2, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 2, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 2, 2, 1, 1, 0, 0, 0, 1, 1, 2, 1, 2, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 1, 1, 0, 1, 2, 1, 0, 0, 1, 2, 2, 1, 2, 1, 1, 2, 2, 1, 1, 0, 1, 2, 1, 0, 1, 0, 0, 1, 2, 1, 1, 0, 0, 0, 0, 1, 1, 2, 3, 4, 5, 5, 5, 4, 4, 4, 3, 3, 2, 2, 2, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 2, 3, 2, 3, 3, 2, 1, 2, 1, 0, 1, 0, 0, 0, 0, 1, 1, 2, 1, 2, 3, 3, 2, 2, 3, 2, 2, 1, 2, 3, 4, 5, 5, 6, 5, 6, 5, 4, 3, 3, 4, 3, 4, 4, 4, 5, 6, 5, 5, 5, 4, 4, 3, 4, 3, 2, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 2, 1, 0, 1, 0, 0, 1, 2, 2, 1, 2, 3, 4, 3, 3, 4, 5, 4, 3, 2, 2, 3, 4, 3, 4, 3, 2, 2, 3, 2, 2, 3, 2, 3, 4, 5, 4, 5, 6, 5, 4, 3, 2, 1, 1, 2, 2, 3, 3, 3, 2, 2, 1, 0, 1, 0, 0, 0, 1, 1, 2, 2, 1, 0, 1, 2, 1, 0, 0, 1, 2, 1, 1, 2, 2, 1, 0, 0, 0, 0, 1, 1, 2, 3, 3, 4, 3, 3, 3, 3, 3, 3, 4, 3, 4, 5, 5, 4, 4, 3, 3, 4, 3, 2, 2, 2, 3, 2, 1, 2, 2, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 1, 1, 2, 2, 3, 2, 1, 2, 2, 2, 3, 2, 2, 3, 2, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 3, 4, 4, 3, 2, 1, 1, 1, 2, 2, 1, 2, 1, 0, 0, 0, 1, 1, 2, 3, 4, 3, 2, 2, 1, 1, 2, 2, 3, 2, 2, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 0, 0, 1, 0, 1, 2, 1, 1, 0, 0, 1, 2, 1, 2, 1, 2, 2, 3, 4, 4, 3, 4, 5, 4, 5, 4, 3, 4, 3, 2, 1, 2, 3, 4, 5, 4, 4, 4, 4, 4, 3, 4, 5, 4, 5, 4, 4, 4, 5, 5, 4, 5, 6, 7, 8, 7, 6, 7, 6, 6, 6, 5, 4, 5, 4, 4, 5, 4, 4, 4, 4, 4, 5, 5, 4, 4, 5, 6, 5, 4, 3, 4, 4, 3, 4, 3, 4, 5, 5, 4, 5, 6, 7, 8, 8, 9, 8, 9, 9, 10, 9, 9, 10, 10, 10, 9, 9, 10, 11, 10, 9, 8, 7, 6, 5, 5, 4, 4, 3, 2, 2, 1, 2, 1, 2, 3, 4, 3, 4, 4, 3, 2, 2, 1, 2, 1, 1, 2, 1, 2, 1, 0, 0, 0, 1, 0, 0, 1, 2, 2, 1, 1, 2, 3, 2, 3, 3, 3, 3, 4, 3, 4, 5, 5, 5, 5, 4, 3, 2, 3, 2, 3, 2, 3, 4, 5, 5, 5, 5, 4, 5, 6, 5, 5, 4, 3, 3, 3, 2, 1, 2, 1, 1, 0, 1, 1, 1, 0, 1, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 2, 2, 3, 2, 2, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 2, 1, 2, 3, 2, 3, 4, 3, 4, 3, 4, 5, 5, 6, 6, 5, 6, 6, 5, 6, 6, 5, 5, 4, 5, 6, 7, 8, 7, 7, 8, 7, 6, 6, 5, 6, 7, 8, 8, 7, 6, 5, 4, 5, 5, 4, 4, 4, 3, 3, 2, 1, 2, 3, 3, 2, 2, 1, 1, 2, 2, 1, 1, 2, 1, 2, 3, 4, 4, 3, 2, 3, 3, 2, 3, 3, 2, 3, 2, 2, 1, 2, 1, 1, 0, 1, 2, 2, 1, 1, 2, 1, 2, 3, 2, 1, 2, 2, 2, 3, 4, 3, 2, 1, 2, 1, 0, 0, 0, 0, 0, 0, 1, 2, 3, 3, 3, 2, 3, 3, 4, 5, 5, 5, 6, 5, 4, 3, 2, 2, 1, 1, 2, 3, 2, 1, 0, 0, 0, 1, 1, 2, 2, 3, 4, 5, 6, 7, 8, 7, 8, 7, 7, 7, 8, 7, 8, 9, 9, 8, 8, 8, 8, 8, 8, 7, 7, 7, 6, 6, 7, 8, 9, 10, 9, 8, 9, 8, 7, 6, 7, 8, 7, 6, 6, 7, 8, 9, 10, 10, 9, 10, 9, 10, 10, 9, 9, 8, 7, 7, 6, 7, 6, 7, 6, 5, 6, 5, 4, 5, 5, 6, 7, 8, 8, 7, 7, 8, 8, 7, 6, 6, 5, 5, 4, 3, 3, 4, 5, 5, 4, 4, 3, 2, 3, 4, 3, 4, 5, 4, 5, 5, 6, 5, 6, 5, 4, 4, 5, 4, 3, 2, 2, 2, 3, 3, 3, 2, 2, 3, 3, 2, 1, 1, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 2, 3, 2, 3, 3, 4, 4, 3, 4, 5, 5, 6, 5, 5, 6, 7, 8, 7, 7, 6, 7, 8, 7, 6, 6, 7, 6, 6, 7, 7, 7, 8, 9, 8, 9, 8, 7, 8, 7, 6, 6, 7, 6, 6, 6, 5, 6, 7, 7, 6, 7, 7, 7, 8, 9, 9, 9, 8, 7, 8, 9, 10, 11, 12, 12, 11, 11, 11, 12, 11, 11, 11, 11, 12, 13, 13, 14, 13, 14, 15, 14, 13, 12, 13, 12, 12, 13, 13, 14, 13, 13, 12, 13, 13, 14, 14, 14, 15, 16, 15, 16, 17, 17, 17, 18, 18, 19, 18, 17, 17, 18, 17, 16, 16, 17, 16, 16, 17, 16, 15, 15, 16, 15, 16, 15, 14, 13, 14, 13, 14, 15, 14, 15, 14, 15, 16, 15, 15, 16, 17, 16, 16, 16, 16, 17, 17, 16, 17, 18, 17, 17, 16, 16, 17, 16, 15, 15, 14, 13, 13, 12, 11, 11, 12, 12, 11, 11, 12, 12, 11, 11, 11, 12, 13, 14, 13, 13, 14, 13, 14, 13, 14, 15, 16, 16, 16, 16, 17, 16, 15, 14, 15, 14, 14, 13, 14, 14, 14, 13, 14, 14, 14, 15, 16, 16, 15, 16, 17, 18, 17, 18, 17, 18, 18, 19, 19, 20, 19, 20, 19, 19, 20, 19, 18, 19, 20, 19, 18, 17, 16, 16, 15, 16, 17, 16, 15, 16, 15, 16, 15, 14, 15, 14, 13, 14, 15, 14, 15, 14, 15, 14, 14, 15, 16, 17, 17, 16, 15, 15, 14, 14, 13, 12, 13, 13, 12, 11, 11, 11, 10, 11, 11, 11, 11, 11, 11, 12, 13, 14, 15, 14, 13, 12, 12, 11, 10, 10, 10, 9, 10, 11, 10, 10, 11, 10, 11, 10, 9, 8, 8, 8, 8, 7, 7, 6, 6, 5, 5, 4, 3, 2, 2, 3, 2, 3, 4, 3, 2, 1, 2, 2, 1, 0, 0, 0, 1, 2, 2, 3, 2, 3, 3, 4, 5, 5, 5, 4, 3, 2, 1, 2, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 2, 3, 4, 3, 3, 3, 4, 5, 5, 4, 3, 2, 2, 3, 2, 1, 1, 2, 1, 0, 0, 1, 2, 2, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 2, 2, 1, 1, 1, 0, 1, 0, 0, 0, 0, 1, 1, 2, 2, 2, 2, 2, 3, 4, 3, 3, 3, 4, 3, 3, 4, 5, 4, 5, 5, 5, 6, 7, 6, 6, 6, 5, 6, 6, 7, 8, 9, 9, 10, 9, 8, 7, 7, 8, 9, 10, 11, 11, 11, 10, 11, 10, 11, 12, 13, 14, 13, 14, 13, 12, 11, 10, 11, 10, 9, 8, 9, 8, 7, 8, 7, 6, 7, 8, 7, 6, 6, 5, 4, 3, 2, 3, 4, 3, 3, 4, 5, 4, 4, 5, 4, 3, 3, 2, 3, 3, 2, 2, 2, 1, 2, 1, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 1, 2, 2, 2, 3, 2, 2, 2, 1, 2, 1, 0, 1, 2, 2, 1, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 2, 2, 1, 0, 0, 1, 2, 2, 3, 4, 5, 6, 5, 5, 4, 4, 3, 3, 3, 2, 2, 2, 2, 2, 3, 3, 2, 3, 3, 3, 2, 1, 0, 0, 0, 0, 0, 0, 1, 2, 2, 3, 3, 2, 3, 4, 4, 4, 4, 4, 5, 6, 5, 5, 6, 6, 6, 7, 6, 6, 7, 8, 7, 8, 7, 8, 9, 10, 9, 8, 7, 7, 8, 7, 8, 9, 9, 8, 8, 7, 8, 9, 9, 8, 8, 7, 8, 7, 6, 5, 5, 5, 6, 7, 6, 7, 8, 8, 9, 10, 10, 9, 8, 9, 9, 10, 10, 11, 10, 10, 9, 8, 8, 8, 8, 9, 8, 7, 7, 7, 8, 7, 6, 5, 6, 6, 6, 5, 4, 4, 4, 3, 4, 3, 2, 1, 2, 1, 1, 2, 1, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 2, 3, 3, 2, 3, 2, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 2, 1, 2, 3, 2, 2, 1, 0, 1, 1, 1, 2, 2, 2, 2, 3, 2, 3, 4, 5, 5, 6, 5, 5, 6, 5, 5, 6, 7, 7, 8, 7, 6, 5, 5, 6, 5, 6, 5, 6, 5, 5, 6, 7, 8, 7, 8, 9, 8, 7, 6, 6, 7, 8, 7, 6, 6, 5, 4, 5, 4, 5, 4, 3, 2, 2, 2, 1, 1, 0, 1, 2, 2, 1, 2, 2, 3, 3, 2, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 2, 3, 2, 3, 2, 3, 2, 2, 1, 0, 0, 0, 0, 0, 1, 1, 2, 3, 4, 3, 3, 2, 1, 2, 3, 2, 2, 2, 3, 4, 5, 5, 5, 4, 4, 5, 6, 7, 6, 5, 5, 5, 5, 4, 3, 2, 1, 0, 0, 1, 2, 1, 0, 0, 0, 0, 0, 1, 1, 1, 2, 2, 1, 2, 3, 2, 3, 2, 1, 0, 1, 1, 1, 1, 0, 1, 1, 2, 3, 3, 3, 4, 3, 2, 2, 2, 1, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 1, 0, 1, 2, 2, 1, 1, 0, 0, 0, 0, 1, 2, 2, 2, 1, 0, 0, 0, 0, 1, 2, 1, 0, 1, 1, 1, 1, 2, 1, 0, 0, 0, 0, 1, 2, 1, 2, 3, 4, 4, 3, 2, 3, 4, 5, 4, 3, 4, 5, 6, 7, 7, 8, 7, 8, 9, 8, 9, 8, 9, 9, 9, 10, 9, 9, 9, 10, 11, 11, 10, 9, 9, 8, 7, 8, 8, 7, 8, 7, 6, 7, 6, 7, 7, 8, 8, 7, 7, 8, 9, 10, 9, 10, 9, 9, 8, 7, 7, 6, 5, 5, 4, 3, 3, 4, 5, 4, 3, 3, 4, 4, 5, 5, 5, 4, 5, 6, 6, 5, 6, 6, 7, 8, 8, 9, 8, 7, 8, 7, 8, 8, 9, 10, 9, 8, 8, 7, 6, 5, 6, 6, 7, 8, 7, 7, 6, 5, 4, 3, 2, 1, 1, 1, 2, 2, 1, 0, 0, 0, 0, 0, 1, 2, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 2, 3, 3, 2, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 2, 1, 2, 2, 2, 3, 2, 2, 3, 2, 3, 2, 1, 2, 3, 3, 4, 4, 4, 4, 3, 2, 3, 2, 2, 2, 3, 3, 3, 3, 2, 3, 2, 2, 1, 1, 0, 0, 0, 0, 0, 1, 2, 1, 2, 1, 2, 3, 2, 1, 2, 1, 1, 0, 0, 1, 0, 0, 0, 1, 2, 1, 0, 0, 0, 0, 0, 1, 2, 1, 1, 1, 1, 2, 3, 4, 4, 5, 5, 6, 5, 4, 4, 4, 3, 3, 3, 2, 1, 1, 0, 0, 0, 1, 0, 1, 2, 3, 2, 3, 4, 5, 6, 5, 5, 4, 3, 4, 5, 5, 4, 5, 5, 4, 4, 5, 6, 6, 5, 4, 4, 3, 3, 4, 3, 4, 3, 3, 3, 4, 3, 4, 3, 2, 2, 3, 3, 4, 3, 2, 2, 2, 2, 3, 3, 2, 3, 2, 1, 1, 0, 1, 1, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 1, 0, 0, 0, 0, 0, 0, 1, 1, 2, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 1, 2, 3, 4, 3, 4, 3, 3, 2, 2, 1, 1, 2, 2, 1, 0, 0, 0, 0, 1, 1, 2, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 2, 1, 0, 1, 0, 1, 0, 0, 0, 0, 1, 1, 1, 2, 2, 2, 3, 4, 5, 4, 3, 2, 1, 2, 3, 3, 4, 3, 2, 1, 1, 0, 1, 2, 3, 2, 3, 2, 1, 0, 0, 0, 1, 2, 2, 3, 3, 2, 1, 0, 1, 2, 2, 3, 3, 2, 2, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 2, 2, 3, 3, 3, 3, 4, 3, 3, 4, 5, 4, 5, 4, 3, 2, 2, 1, 0, 0, 0, 1, 2, 1, 0, 0, 1, 2, 1, 2, 3, 2, 2, 3, 3, 2, 1, 2, 3, 3, 4, 3, 2, 3, 2, 1, 1, 1, 1, 2, 3, 2, 2, 2, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 2, 2, 1, 2, 1, 2, 2, 1, 0, 0, 0, 1, 2, 1, 2, 3, 3, 2, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 2, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 0, 1, 1, 2, 2, 3, 4, 3, 2, 3, 2, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 2, 3, 2, 3, 4, 5, 6, 5, 5, 5, 5, 4, 3, 4, 3, 2, 3, 2, 2, 1, 1, 2, 2, 2, 3, 4, 5, 4, 4, 5, 5, 6, 5, 4, 5, 4, 3, 3, 4, 3, 3, 4, 5, 6, 7, 7, 7, 7, 7, 6, 7, 8, 7, 8, 7, 8, 9, 9, 8, 8, 8, 8, 7, 7, 8, 8, 8, 7, 8, 7, 8, 7, 6, 5, 5, 4, 4, 5, 4, 5, 6, 5, 4, 5, 4, 3, 3, 2, 2, 3, 4, 4, 3, 3, 4, 5, 4, 4, 3, 4, 4, 3, 4, 3, 3, 2, 1, 2, 1, 2, 1, 2, 2, 3, 4, 4, 3, 2, 3, 3, 3, 2, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 2, 3, 4, 5, 6, 5, 6, 5, 6, 6, 7, 6, 6, 7, 6, 5, 5, 6, 6, 5, 6, 5, 4, 3, 2, 3, 4, 5, 4, 4, 3, 4, 3, 2, 3, 4, 3, 4, 5, 4, 3, 2, 3, 3, 4, 5, 4, 4, 4, 4, 5, 5, 5, 6, 5, 4, 5, 6, 7, 6, 5, 4, 3, 3, 4, 3, 3, 4, 4, 4, 4, 3, 2, 1, 0, 0, 1, 2, 3, 4, 3, 3, 4, 5, 6, 7, 8, 8, 9, 9, 8, 9, 8, 8, 7, 6, 5, 5, 5, 5, 4, 4, 3, 2, 2, 1, 2, 1, 0, 1, 1, 2, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 1, 0, 1, 1, 2, 2, 2, 3, 4, 4, 4, 3, 3, 3, 2, 1, 2, 1, 0, 1, 0, 1, 1, 0, 0, 0, 1, 1, 2, 3, 2, 2, 1, 0, 0, 0, 0, 1, 1, 2, 2, 3, 2, 3, 3, 4, 5, 4, 4, 5, 6, 5, 6, 7, 8, 8, 9, 9, 9, 8, 8, 7, 7, 7, 6, 5, 6, 6, 6, 5, 6, 6, 5, 4, 3, 3, 2, 3, 3, 4, 4, 4, 3, 3, 2, 3, 3, 2, 3, 2, 2, 2, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 2, 2, 3, 2, 1, 0, 0, 1, 2, 1, 2, 3, 3, 4, 3, 2, 1, 2, 2, 1, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 2, 1, 1, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 1, 1, 0, 1, 2, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 1, 2, 3, 4, 3, 3, 4, 5, 4, 5, 5, 6, 5, 5, 4, 5, 6, 5, 5, 4, 4, 3, 2, 3, 3, 2, 1, 1, 2, 1, 0, 0, 0, 1, 1, 2, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 2, 1, 0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 2, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 1, 2, 2, 3, 2, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 1, 2, 1, 2, 3, 2, 3, 2, 2, 1, 0, 0, 1, 2, 2, 1, 0, 1, 2, 3, 2, 1, 1, 2, 1, 2, 3, 4, 5, 4, 3, 2, 1, 1, 2, 3, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 2, 2, 1, 0, 0, 1, 2, 3, 2, 2, 2, 3, 3, 2, 3, 3, 4, 5, 6, 7, 8, 7, 7, 7, 8, 7, 6, 5, 6, 5, 5, 6, 6, 7, 7, 7, 7, 8, 9, 8, 7, 7, 7, 8, 7, 6, 6, 5, 6, 6, 7, 6, 6, 7, 8, 8, 9, 9, 10, 9, 8, 9, 9, 9, 8, 8, 9, 9, 9, 10, 9, 8, 8, 7, 6, 7, 6, 6]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "N=len(qdata)\n",
    "max(qdata)\n",
    "N1=N\n",
    "print(N1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Estimate probabilities p1,p2\n",
    "# for transition k-> k-1,k or k for k>0 only\n",
    "\n",
    "nup=0 # nup counts no of up steps k->k+1 for k>0\n",
    "ndown=0 # ndown counts no of down steps k->k-1 for k>0\n",
    "nn0=0 # no k>0 data points\n",
    "\n",
    "for i in range(1,N-1): \n",
    "    if qdata[i]>0: \n",
    "        nn0=nn0+1 # count non zero data\n",
    "        if qdata[i]<qdata[i+1]:\n",
    "            nup=nup+1\n",
    "        elif qdata[i]>qdata[i+1]:\n",
    "            ndown=ndown+1\n",
    "print(nup,\"up steps\", ndown,\"down steps\",nn0, \"non zero data points\")\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "p1=nup/nn0\n",
    "p2=ndown/nn0\n",
    "print(p1,p2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "Qplot(qdata)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Q.4 (*)\n",
    "### Telephone Exchange Queue.\n",
    "A telephone exchange consists of $N$\n",
    "operators on $N$ lines. Assume that the calling and servicing patterns are\n",
    "Poisson with parameters $\\alpha _{k}=\\alpha ,\\ \\beta _{k}=k\\beta $\n",
    "respectively for queue size of $0\\leq k\\leq N$ and for some $\\alpha, \\beta >0$.\n",
    "The equilibrium distribution for the queue is: \n",
    "$$\n",
    "\\pi _{k}=\\frac{\\rho ^{k}}{k!}\\left(1+\\rho +\\frac{\\rho ^{2}}{2!}+...+\\frac{\\rho\n",
    "^{N}}{N!}\\right)^{-1},\\ \\rho =\\ \\frac{\\alpha }{\\beta } \n",
    "$$\n",
    "Of particular interest, in this model, is the frequency with which the\n",
    "exchange becomes saturated over a long period of time i.e. $\\pi_N.$ This\n",
    "should be a small number for an efficient exchange since it provides a\n",
    "measurement of the number of calls lost to the system.\n",
    "\n",
    "   1. A telephone exchange has 5 operators who can handle 40 calls an hour each on average. If calls arrive at the exchange on average every 40 secs, show that there is approximately a 5.2\\% chance that the exchange will become saturated after a long time.\n",
    "\n",
    "   2. Simulate this system over 3 hours with 10 sec time intervals. For what proportion of your simulated events do you find all operators are busy?\n",
    "   \n",
    "   3. Compare the results of your simulation to the equilibirum probabilities $\\pi_{k}$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Hints\n",
    "Calculate $\\alpha,\\beta$ based on the information given for the 5 operator exchange. Be consistent with use of time units. In part (2) choose 10 secs as the time interval size and construct a transition matrix $P$ before simulating.\n",
    "\n",
    "The factorial function in Python is computed using `math.factorial` e.g"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "math.factorial(5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.11.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}