/*
 * (C) Copyright 2018-2023, by Timofey Chudakov and Contributors.
 *
 * JGraphT : a free Java graph-theory library
 *
 * See the CONTRIBUTORS.md file distributed with this work for additional
 * information regarding copyright ownership.
 *
 * This program and the accompanying materials are made available under the
 * terms of the Eclipse Public License 2.0 which is available at
 * http://www.eclipse.org/legal/epl-2.0, or the
 * GNU Lesser General Public License v2.1 or later
 * which is available at
 * http://www.gnu.org/licenses/old-licenses/lgpl-2.1-standalone.html.
 *
 * SPDX-License-Identifier: EPL-2.0 OR LGPL-2.1-or-later
 */
package org.jgrapht.alg.flow.mincost;

import org.jgrapht.*;
import org.jgrapht.alg.interfaces.MinimumCostFlowAlgorithm.*;
import org.jgrapht.graph.*;
import org.junit.*;
import org.junit.runner.*;
import org.junit.runners.*;

import java.util.*;

import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertTrue;

/**
 * Unit tests for {@link CapacityScalingMinimumCostFlow}
 *
 * @author Timofey Chudakov
 */
@RunWith(Parameterized.class)
public class CapacityScalingMinimumCostFlowTest
{

    private static final double EPS = 1e-9;
    private int scalingFactor;

    public CapacityScalingMinimumCostFlowTest(int scalingFactor)
    {
        this.scalingFactor = scalingFactor;
    }

    @Parameterized.Parameters
    public static Object[] params()
    {
        return new Integer[] { 1, 2, 3, 4, 5 };
    }

    @Test
    public void testGetMinimumCostFlow1()
    {
        int[][] testCase = new int[][] { { 1, 3 }, { 2, -3 }, { 1, 2, 0, 4, 5 } };
        test(testCase, 15);
    }

    @Test
    public void testGetMinimumCostFlow2()
    {
        int[][] testCase = new int[][] { { 1, 4 }, { 4, -4 }, { 1, 2, 0, 4, 2 }, { 1, 3, 0, 1, 3 },
            { 2, 3, 0, 1, 1 }, { 2, 4, 0, 5, 6 }, { 3, 4, 0, 4, 2 } };
        test(testCase, 26);
    }

    @Test
    public void testGetMinimumCostFlow3()
    {
        int[][] testCase =
            new int[][] { { 1, 2 }, { 2, 5 }, { 6, -7 }, { 1, 5, 0, 3, 6 }, { 3, 6, 0, 3, 9 },
                { 3, 1, 0, 3, 6 }, { 5, 3, 0, 3, 4 }, { 5, 6, 0, 7, 4 }, { 2, 4, 0, 5, 10 },
                { 2, 3, 0, 1, 3 }, { 4, 6, 0, 5, 10 }, { 4, 1, 0, 5, 3 }, { 4, 3, 0, 1, 8 }, };
        test(testCase, 112);
    }

    /**
     * Test case generated with NETGEN generator params: vertices = 6, edges = 12, sources = 2,
     * sinks = 2, supply = 10, min. capacity = 1, max. capacity = 10, min. cost = 1, max. cost = 10,
     * capacitated = 50%, seed = 1
     */
    @Test
    public void testGetMinimumCostFlow4()
    {
        int testCase[][] = new int[][] { { 1, 2731 }, { 2, 414 }, { 3, -1264 }, { 4, 216 },
            { 5, -1785 }, { 6, -312 }, { 1, 4, 910, 2147483647, 10 }, { 1, 5, 957, 2147483647, 1 },
            { 1, 3, 863, 2147483647, 3 }, { 3, 5, 1, 1, -5 }, { 3, 6, 1, 1, 10 }, { 3, 4, 1, 9, 2 },
            { 4, 3, 1, 1, 8 }, { 4, 5, 820, 2147483647, 4 }, { 4, 6, 306, 2147483647, 7 },
            { 2, 5, 1, 9, 7 }, { 2, 6, 1, 9, 10 }, { 2, 3, 403, 2147483647, 6 }, };
        test(testCase, 20594);
    }

    /**
     * Test case generated with NETGEN generator params: vertices = 8, edges = 16, sources = 2,
     * sinks = 2, supply = 15, min. capacity = 1, max. capacity = 10, min. cost = 1, max. cost = 10,
     * capacitated = 50%, seed = 1
     */
    @Test
    public void testGetMinimumCostFlow5()
    {
        int testCase[][] = new int[][] { { 1, 635 }, { 2, 980 }, { 3, 1658 }, { 4, -462 },
            { 5, -821 }, { 6, -1123 }, { 7, -13 }, { 8, -854 }, { 1, 5, 625, 2147483647, 10 },
            { 1, 7, 1, 8, 2 }, { 3, 4, 805, 2147483647, 10 }, { 3, 6, 855, 2147483647, 3 },
            { 4, 8, 847, 2147483647, 5 }, { 4, 7, 1, 9, 9 }, { 4, 5, 197, 2147483647, 4 },
            { 5, 3, 1, 9, 1 }, { 5, 7, 1, 4, 3 }, { 2, 6, 973, 2147483647, 10 }, { 2, 4, 1, 4, 10 },
            { 6, 7, 1, 6, 10 }, { 6, 8, 1, 6, 8 }, { 6, 3, 1, 6, 2 }, { 6, 5, 1, 10, 5 },
            { 6, 4, 701, 2147483647, 2 }, };
        test(testCase, 33206);
    }

    /**
     * Test case generated with NETGEN generator params: vertices = 6, edges = 12, sources = 2,
     * sinks = 2, supply = 10, min. capacity = 1, max. capacity = 10, min. cost = 1, max. cost = 10,
     * capacitated = 50%, seed = 1
     */
    @Test
    public void testGetMinimumCostFlow6()
    {
        int testCase[][] = new int[][] { { 1, 10 }, { 2, 6 }, { 3, -211 }, { 4, 506 }, { 5, -10 },
            { 6, -301 }, { 1, 3, 1, 7, 10 }, { 1, 5, 1, 2, 4 }, { 1, 4, 1, 1, 6 },
            { 3, 4, 1, 7, 3 }, { 3, 6, 295, 2147483647, 10 }, { 3, 5, 1, 8, 1 }, { 4, 5, 1, 7, 10 },
            { 4, 3, 506, 2147483647, 8 }, { 4, 6, 1, 1, -10 }, { 2, 5, 1, 3, 2 },
            { 2, 6, 1, 3, 10 }, { 2, 3, 1, 10, 10 }, };
        test(testCase, 7154);
    }

    /**
     * Test case generated with NETGEN generator params: vertices = 6, edges = 12, sources = 2,
     * sinks = 2, supply = 10, min. capacity = 1, max. capacity = 10, min. cost = 1, max. cost = 10,
     * capacitated = 100%, seed = 1
     */
    @Test
    public void testGetMinimumCostFlow7()
    {
        scalingFactor = 2;
        int testCase[][] = new int[][] { { 1, 7 }, { 2, 1430 }, { 3, -1350 }, { 4, 840 },
            { 5, -499 }, { 6, -428 }, { 1, 3, 1, 4, 10 }, { 1, 4, 1, 10, 10 }, { 1, 5, 1, 10, 9 },
            { 3, 4, 1, 4, 10 }, { 3, 6, 1, 1, -3 }, { 3, 5, 489, 2147483647, 6 },
            { 4, 6, 1, 4, 10 }, { 4, 5, 1, 4, 1 }, { 4, 3, 840, 2147483647, 10 },
            { 2, 6, 423, 2147483647, 10 }, { 2, 5, 1, 6, 10 }, { 2, 3, 1000, 2147483647, 9 }, };
        test(testCase, 24717);
    }

    /**
     * Test case generated with NETGEN generator params: vertices = 6, edges = 12, sources = 2,
     * sinks = 2, supply = 10, min. capacity = 1, max. capacity = 10, min. cost = 1, max. cost = 10,
     * capacitated = 100%, seed = 1
     */
    @Test
    public void testGetMinimumCostFlow8()
    {
        int testCase[][] = new int[][] { { 1, 7 }, { 2, 1294 }, { 3, -332 }, { 4, 265 },
            { 5, -460 }, { 6, -774 }, { 1, 3, 1, 4, 10 }, { 1, 4, 1, 10, 10 }, { 1, 5, 1, 10, 9 },
            { 3, 4, 1, 4, 10 }, { 3, 6, 1, 8, 3 }, { 3, 5, 450, 2147483647, 6 },
            { 4, 6, 1, 4, -10 }, { 4, 5, 1, 4, 1 }, { 4, 3, 265, 2147483647, 10 },
            { 2, 6, 769, 2147483647, 10 }, { 2, 5, 1, 6, 10 }, { 2, 3, 518, 2147483647, 9 }, };
        test(testCase, 17819);
    }

    /**
     * Test case generated with NETGEN generator params: vertices = 6, edges = 12, sources = 2,
     * sinks = 2, supply = 10, min. capacity = 1, max. capacity = 10, min. cost = 1, max. cost = 10,
     * capacitated = 50%, seed = 1
     */
    @Test
    public void testGetMinimumCostFlow9()
    {
        int testCase[][] = new int[][] { { 1, 7 }, { 2, 763 }, { 3, -637 }, { 4, 164 }, { 5, -138 },
            { 6, -159 }, { 1, 3, 1, 4, 10 }, { 1, 4, 1, 2, -10 }, { 1, 5, 1, 10, 9 },
            { 3, 4, 1, 4, 10 }, { 3, 6, 1, 8, 3 }, { 3, 5, 128, 2147483647, 6 }, { 4, 6, 1, 4, 10 },
            { 4, 5, 1, 4, 1 }, { 4, 3, 164, 2147483647, 10 }, { 2, 6, 154, 2147483647, 10 },
            { 2, 5, 1, 6, 10 }, { 2, 3, 602, 2147483647, 9 }, };
        test(testCase, 9487);
    }

    /**
     * Test case generated with NETGEN generator params: vertices = 10, edges = 30, sources = 3,
     * sinks = 3, supply = 30, min. capacity = 1, max. capacity = 50, min. cost = 1, max. cost = 50,
     * capacitated = 50%, seed = 268101079
     */
    @Test
    public void testGetMinimumCostFlow10()
    {
        int testCase[][] = new int[][] { { 1, 8 }, { 2, 16 }, { 3, 6 }, { 8, -16 }, { 9, -6 },
            { 10, -8 }, { 1, 5, 0, 2147483647, 50 }, { 1, 7, 0, 5, 32 }, { 1, 9, 0, 18, 33 },
            { 1, 8, 0, 2147483647, 31 }, { 1, 4, 0, 45, 35 }, { 5, 6, 0, 8, 50 },
            { 5, 10, 0, 2147483647, 2 }, { 5, 8, 0, 11, 18 }, { 5, 7, 0, 21, 44 },
            { 5, 9, 0, 2147483647, 22 }, { 5, 4, 0, 35, 48 }, { 6, 8, 0, 8, 19 },
            { 6, 9, 0, 2147483647, 20 }, { 6, 4, 0, 2147483647, 47 }, { 6, 5, 0, 26, 22 },
            { 6, 10, 0, 9, 5 }, { 6, 7, 0, 47, 46 }, { 2, 4, 0, 2147483647, 50 },
            { 2, 7, 0, 2147483647, 17 }, { 2, 9, 0, 25, 28 }, { 2, 6, 0, 8, 3 },
            { 4, 7, 0, 2147483647, 18 }, { 4, 10, 0, 16, 33 }, { 4, 8, 0, 2147483647, 6 },
            { 4, 9, 0, 12, 13 }, { 7, 9, 0, 16, 50 }, { 7, 8, 0, 2147483647, 50 },
            { 3, 10, 0, 6, 21 }, { 3, 8, 0, 6, 50 }, { 3, 7, 0, 33, 37 }, };
        test(testCase, 802);
    }

    /**
     * Test case generated with NETGEN generator params: vertices = 10, edges = 30, sources = 3,
     * sinks = 3, supply = 30, min. capacity = 1, max. capacity = 50, min. cost = 1, max. cost =
     * 100, capacitated = 50%, seed = 651272247
     */
    @Test
    public void testGetMinimumCostFlow11()
    {
        int testCase[][] = new int[][] { { 1, 1 }, { 2, 23 }, { 3, 6 }, { 8, -17 }, { 9, -9 },
            { 10, -4 }, { 1, 7, 0, 1, 100 }, { 1, 6, 0, 10, 15 }, { 1, 4, 0, 37, 72 },
            { 5, 10, 0, 2147483647, 81 }, { 5, 9, 0, 2147483647, 10 }, { 5, 8, 0, 1, 100 },
            { 5, 6, 0, 27, 85 }, { 5, 4, 0, 2147483647, 87 }, { 7, 5, 0, 1, 100 },
            { 7, 6, 0, 2147483647, 25 }, { 2, 6, 0, 23, 29 }, { 2, 7, 0, 2147483647, 34 },
            { 6, 9, 0, 2147483647, 100 }, { 6, 8, 0, 2147483647, 56 }, { 6, 5, 0, 15, 32 },
            { 6, 10, 0, 2147483647, 76 }, { 6, 7, 0, 10, 36 }, { 6, 4, 0, 2147483647, 66 },
            { 3, 4, 0, 2147483647, 26 }, { 3, 5, 0, 32, 27 }, { 3, 8, 0, 41, 75 },
            { 3, 7, 0, 2147483647, 80 }, { 3, 9, 0, 2147483647, 63 }, { 3, 6, 0, 30, 64 },
            { 4, 9, 0, 2147483647, 13 }, { 4, 10, 0, 2147483647, 100 }, { 4, 5, 0, 25, 20 },
            { 4, 8, 0, 2147483647, 100 }, { 4, 7, 0, 2147483647, 1 }, { 4, 6, 0, 2147483647, 59 },

        };
        test(testCase, 2286);
    }

    /**
     * Test case generated with NETGEN generator params: vertices = 30, edges = 100, sources = 5,
     * sinks = 5, supply = 50, min. capacity = 1, max. capacity = 100, min. cost = 1, max. cost =
     * 100, capacitated = 100%, seed = 1685408561
     */
    @Test
    public void testGetMinimumCostFlow12()
    {
        int testCase[][] = new int[][] { { 1, 8 }, { 2, 10 }, { 3, 9 }, { 4, 18 }, { 5, 5 },
            { 26, -9 }, { 27, -15 }, { 28, -4 }, { 29, -6 }, { 30, -16 },
            { 1, 11, 0, 2147483647, 85 }, { 1, 18, 0, 12, 24 }, { 1, 24, 0, 2147483647, 92 },
            { 1, 29, 0, 15, 48 }, { 1, 14, 0, 49, 80 }, { 11, 16, 0, 8, 100 },
            { 11, 21, 0, 94, 18 }, { 11, 26, 0, 2147483647, 36 }, { 11, 12, 0, 2147483647, 21 },
            { 11, 23, 0, 12, 18 }, { 14, 26, 0, 8, 51 }, { 14, 20, 0, 32, 49 },
            { 14, 10, 0, 2147483647, 91 }, { 14, 11, 0, 9, 59 }, { 16, 14, 0, 8, 42 },
            { 16, 30, 0, 8, 100 }, { 16, 27, 0, 86, 3 }, { 2, 20, 0, 2147483647, 100 },
            { 2, 7, 0, 2147483647, 58 }, { 8, 24, 0, 2147483647, 100 }, { 8, 12, 0, 18, 13 },
            { 8, 6, 0, 23, 51 }, { 8, 7, 0, 2147483647, 17 }, { 8, 26, 0, 88, 37 },
            { 13, 8, 0, 10, 100 }, { 13, 17, 0, 58, 69 }, { 20, 13, 0, 2147483647, 100 },
            { 20, 18, 0, 2147483647, 10 }, { 24, 28, 0, 10, 100 }, { 24, 30, 0, 2147483647, 100 },
            { 24, 27, 0, 2147483647, 48 }, { 24, 22, 0, 2147483647, 22 }, { 24, 12, 0, 71, 81 },
            { 24, 11, 0, 68, 20 }, { 3, 9, 0, 9, 2 }, { 3, 16, 0, 2147483647, 17 },
            { 3, 14, 0, 67, 84 }, { 3, 17, 0, 19, 69 }, { 3, 11, 0, 87, 54 },
            { 3, 23, 0, 2147483647, 23 }, { 3, 15, 0, 2, 41 }, { 6, 17, 0, 2147483647, 21 },
            { 6, 13, 0, 2147483647, 4 }, { 6, 26, 0, 90, 65 }, { 7, 18, 0, 9, 100 },
            { 7, 9, 0, 24, 64 }, { 9, 6, 0, 2147483647, 83 }, { 9, 7, 0, 2147483647, 93 },
            { 9, 19, 0, 99, 51 }, { 9, 18, 0, 2147483647, 26 }, { 9, 14, 0, 2147483647, 61 },
            { 17, 7, 0, 2147483647, 66 }, { 17, 11, 0, 92, 90 }, { 17, 19, 0, 2147483647, 36 },
            { 18, 30, 0, 2147483647, 96 }, { 18, 27, 0, 9, 42 }, { 18, 21, 0, 58, 46 },
            { 18, 14, 0, 2147483647, 77 }, { 18, 12, 0, 96, 69 }, { 4, 19, 0, 2147483647, 50 },
            { 4, 27, 0, 18, 54 }, { 4, 14, 0, 2147483647, 71 }, { 4, 20, 0, 2147483647, 47 },
            { 4, 23, 0, 67, 85 }, { 4, 29, 0, 62, 47 }, { 4, 24, 0, 2147483647, 31 },
            { 10, 29, 0, 2147483647, 99 }, { 10, 23, 0, 2147483647, 12 }, { 10, 19, 0, 51, 13 },
            { 10, 24, 0, 2147483647, 21 }, { 10, 22, 0, 62, 5 }, { 12, 27, 0, 2147483647, 28 },
            { 12, 23, 0, 2147483647, 75 }, { 12, 14, 0, 26, 37 }, { 12, 25, 0, 2147483647, 97 },
            { 12, 17, 0, 2147483647, 46 }, { 15, 10, 0, 18, 100 }, { 15, 29, 0, 2147483647, 67 },
            { 15, 12, 0, 2147483647, 73 }, { 15, 17, 0, 28, 97 }, { 19, 12, 0, 18, 100 },
            { 19, 15, 0, 2147483647, 22 }, { 19, 25, 0, 92, 71 }, { 19, 13, 0, 28, 41 },
            { 19, 23, 0, 2147483647, 98 }, { 21, 15, 0, 2147483647, 100 },
            { 21, 26, 0, 2147483647, 76 }, { 21, 30, 0, 91, 1 }, { 21, 13, 0, 33, 6 },
            { 23, 21, 0, 2147483647, 91 }, { 23, 19, 0, 36, 76 }, { 23, 11, 0, 25, 54 },
            { 5, 25, 0, 5, 89 }, { 5, 20, 0, 16, 6 }, { 22, 29, 0, 2147483647, 66 },
            { 22, 28, 0, 5, 100 }, { 22, 13, 0, 2147483647, 1 }, { 22, 11, 0, 2147483647, 97 },
            { 25, 22, 0, 5, 100 }, { 25, 14, 0, 2147483647, 73 },

        };
        test(testCase, 4067);
    }

    /**
     * Test case generated with NETGEN generator params: vertices = 30, edges = 100, sources = 5,
     * sinks = 5, supply = 50, min. capacity = 1, max. capacity = 100, min. cost = 1, max. cost =
     * 100, capacitated = 50%, seed = 843930509
     */
    @Test
    public void testGetMinimumCostFlow13()
    {
        int testCase[][] = new int[][] { { 1, 1391 }, { 2, 790 }, { 3, 1671 }, { 4, 815 },
            { 5, 342 }, { 6, -148 }, { 7, 1254 }, { 8, 848 }, { 9, 169 }, { 10, -282 }, { 11, 978 },
            { 12, 956 }, { 13, 127 }, { 14, 493 }, { 15, -1432 }, { 16, 1224 }, { 17, 725 },
            { 18, 286 }, { 19, 1092 }, { 20, -1069 }, { 21, -3223 }, { 22, 49 }, { 23, -510 },
            { 24, 1927 }, { 25, -757 }, { 26, -495 }, { 27, -179 }, { 28, -1988 }, { 29, -2288 },
            { 30, -2766 }, { 1, 10, 494, 2147483647, 61 }, { 1, 15, 1, 29, 3 },
            { 1, 22, 1, 31, 34 }, { 1, 19, 884, 2147483647, 13 }, { 10, 21, 1, 11, 80 },
            { 10, 13, 455, 2147483647, 97 }, { 10, 16, 19, 2147483647, 80 },
            { 10, 18, 417, 2147483647, 23 }, { 10, 23, 673, 2147483647, 83 }, { 11, 16, 1, 11, 9 },
            { 11, 29, 502, 2147483647, 100 }, { 11, 20, 1, 29, 14 },
            { 11, 21, 364, 2147483647, 70 }, { 11, 27, 112, 2147483647, 37 },
            { 16, 30, 348, 2147483647, 21 }, { 16, 23, 1, 37, 74 }, { 16, 15, 912, 2147483647, 9 },
            { 16, 22, 31, 2147483647, 43 }, { 16, 7, 599, 2147483647, 65 }, { 21, 11, 1, 11, 100 },
            { 21, 27, 1, 15, 5 }, { 21, 16, 1, 72, 33 }, { 21, 15, 1, 55, 14 },
            { 2, 14, 779, 2147483647, 100 }, { 2, 24, 1, 36, 69 }, { 6, 13, 816, 2147483647, 71 },
            { 6, 16, 541, 2147483647, 27 }, { 6, 10, 1, 64, 48 }, { 6, 26, 1, 2, 82 },
            { 13, 23, 418, 2147483647, 100 }, { 13, 15, 978, 2147483647, 45 }, { 13, 7, 1, 27, 29 },
            { 13, 11, 1, 98, 75 }, { 13, 6, 1, 7, 75 }, { 14, 19, 364, 2147483647, 100 },
            { 14, 26, 1, 47, 62 }, { 14, 24, 1, 39, 77 }, { 14, 22, 907, 2147483647, 49 },
            { 19, 6, 999, 2147483647, 40 }, { 19, 27, 1, 10, 100 }, { 19, 7, 1, 33, 76 },
            { 19, 25, 966, 2147483647, 30 }, { 19, 20, 375, 2147483647, 91 },
            { 23, 29, 77, 2147483647, 100 }, { 23, 12, 1, 40, 93 }, { 23, 6, 505, 2147483647, 95 },
            { 3, 24, 1, 10, 100 }, { 3, 27, 46, 2147483647, 51 }, { 3, 28, 758, 2147483647, 38 },
            { 3, 9, 856, 2147483647, 36 }, { 8, 30, 967, 2147483647, 29 }, { 8, 17, 1, 10, 40 },
            { 8, 22, 1, 42, 7 }, { 8, 9, 606, 2147483647, 19 }, { 17, 18, 1, 10, 31 },
            { 17, 20, 725, 2147483647, 4 }, { 18, 20, 629, 2147483647, 100 },
            { 18, 28, 884, 2147483647, 31 }, { 18, 10, 1, 43, 49 }, { 18, 27, 1, 16, 4 },
            { 20, 27, 1, 10, 100 }, { 20, 30, 661, 2147483647, 55 },
            { 22, 8, 726, 2147483647, 100 }, { 22, 10, 429, 2147483647, 66 },
            { 22, 26, 2, 100, 92 }, { 22, 29, 1, 80, 19 }, { 22, 20, 1, 43, 9 },
            { 22, 12, 790, 2147483647, 75 }, { 22, 19, 1, 82, 86 },
            { 24, 22, 960, 2147483647, 100 }, { 24, 16, 26, 2147483647, 35 },
            { 24, 21, 943, 2147483647, 7 }, { 24, 13, 1, 42, 4 }, { 4, 9, 807, 2147483647, 100 },
            { 4, 22, 1, 52, 13 }, { 4, 12, 1, 77, 66 }, { 4, 8, 1, 52, 5 }, { 7, 27, 1, 5, 100 },
            { 7, 29, 562, 2147483647, 100 }, { 7, 6, 1, 46, 56 }, { 7, 15, 370, 2147483647, 65 },
            { 7, 10, 922, 2147483647, 73 }, { 9, 25, 682, 2147483647, 33 },
            { 9, 30, 781, 2147483647, 98 }, { 9, 23, 1, 77, 77 }, { 9, 21, 974, 2147483647, 58 },
            { 25, 7, 1, 5, 45 }, { 25, 18, 811, 2147483647, 54 }, { 25, 16, 79, 2147483647, 64 },
            { 5, 12, 325, 2147483647, 100 }, { 5, 6, 1, 79, 7 }, { 5, 14, 1, 45, 83 },
            { 5, 21, 1, 91, 21 }, { 12, 15, 737, 2147483647, 100 }, { 12, 29, 391, 2147483647, 86 },
            { 12, 19, 1, 51, 39 }, { 12, 21, 944, 2147483647, 29 },
            { 15, 28, 340, 2147483647, 100 }, { 15, 29, 743, 2147483647, 48 },
            { 15, 26, 484, 2147483647, 100 }, };
        test(testCase, 1982153);
    }

    /**
     * Test case generated with NETGEN generator params: vertices = 50, edges = 154, sources = 20,
     * sinks = 20, supply = 200, min. capacity = 1, max. capacity = 1000, min. cost = 1, max. cost =
     * 100, capacitated = 10%, seed = 1342893451
     */
    @Test
    public void testGetMinimumCostFlow14()
    {
        int testCase[][] = new int[][] { { 1, 11 }, { 2, 25 }, { 3, 9 }, { 4, 10 }, { 5, 10 },
            { 6, 5 }, { 7, 6 }, { 8, 10 }, { 9, 4 }, { 10, 18 }, { 11, 7 }, { 12, 9 }, { 13, 8 },
            { 14, 19 }, { 15, 10 }, { 16, 13 }, { 17, 1 }, { 18, 7 }, { 19, 13 }, { 20, 5 },
            { 31, -11 }, { 32, -5 }, { 33, -9 }, { 34, -2 }, { 35, -8 }, { 36, -2 }, { 37, -13 },
            { 38, -7 }, { 39, -11 }, { 40, -10 }, { 42, -28 }, { 43, -13 }, { 44, -15 },
            { 45, -22 }, { 46, -10 }, { 47, -8 }, { 49, -15 }, { 50, -11 },
            { 1, 25, 0, 2147483647, 38 }, { 1, 31, 0, 2147483647, 93 },
            { 1, 45, 0, 2147483647, 47 }, { 1, 21, 0, 2147483647, 18 }, { 25, 45, 0, 11, 14 },
            { 25, 43, 0, 11, 100 }, { 25, 39, 0, 2147483647, 69 }, { 25, 42, 0, 2147483647, 38 },
            { 25, 29, 0, 216, 31 }, { 2, 21, 0, 25, 46 }, { 2, 33, 0, 973, 72 },
            { 2, 37, 0, 150, 10 }, { 2, 39, 0, 2147483647, 67 }, { 2, 32, 0, 994, 9 },
            { 2, 29, 0, 11, 24 }, { 21, 47, 0, 25, 100 }, { 21, 44, 0, 25, 100 },
            { 21, 31, 0, 25, 34 }, { 21, 46, 0, 25, 100 }, { 21, 29, 0, 879, 15 },
            { 21, 35, 0, 2147483647, 23 }, { 21, 42, 0, 321, 64 }, { 21, 38, 0, 2147483647, 27 },
            { 21, 27, 0, 2147483647, 13 }, { 21, 45, 0, 160, 60 }, { 3, 23, 0, 2147483647, 100 },
            { 3, 48, 0, 104, 88 }, { 3, 25, 0, 967, 18 }, { 3, 46, 0, 72, 53 },
            { 23, 33, 0, 2147483647, 15 }, { 23, 46, 0, 9, 30 }, { 23, 44, 0, 2147483647, 100 },
            { 23, 31, 0, 9, 98 }, { 23, 24, 0, 556, 25 }, { 23, 47, 0, 2147483647, 19 },
            { 23, 35, 0, 509, 19 }, { 23, 50, 0, 2147483647, 14 }, { 23, 40, 0, 82, 18 },
            { 23, 42, 0, 21, 74 }, { 4, 30, 0, 2147483647, 100 }, { 4, 41, 0, 389, 4 },
            { 4, 24, 0, 2147483647, 22 }, { 30, 40, 0, 2147483647, 57 }, { 30, 37, 0, 10, 7 },
            { 30, 36, 0, 2147483647, 100 }, { 30, 34, 0, 10, 59 }, { 30, 49, 0, 523, 19 },
            { 30, 47, 0, 2147483647, 25 }, { 30, 45, 0, 2147483647, 26 }, { 5, 24, 0, 10, 94 },
            { 5, 23, 0, 649, 62 }, { 5, 28, 0, 2147483647, 71 }, { 5, 34, 0, 880, 4 },
            { 5, 36, 0, 2147483647, 73 }, { 5, 46, 0, 835, 65 }, { 24, 32, 0, 10, 100 },
            { 24, 31, 0, 2147483647, 100 }, { 24, 50, 0, 2147483647, 100 },
            { 24, 46, 0, 2147483647, 44 }, { 24, 26, 0, 2147483647, 50 },
            { 24, 27, 0, 2147483647, 17 }, { 24, 22, 0, 2147483647, 51 }, { 24, 33, 0, 175, 96 },
            { 24, 44, 0, 2147483647, 21 }, { 6, 26, 0, 2147483647, 100 }, { 6, 29, 0, 836, 13 },
            { 26, 29, 0, 5, 34 }, { 26, 42, 0, 5, 93 }, { 26, 33, 0, 2147483647, 19 },
            { 26, 48, 0, 5, 28 }, { 26, 45, 0, 5, 100 }, { 26, 31, 0, 2147483647, 51 },
            { 26, 21, 0, 2147483647, 53 }, { 26, 46, 0, 2147483647, 54 },
            { 29, 49, 0, 2147483647, 100 }, { 29, 35, 0, 2147483647, 100 }, { 29, 50, 0, 5, 91 },
            { 29, 46, 0, 5, 100 }, { 29, 45, 0, 2147483647, 79 }, { 29, 25, 0, 328, 76 },
            { 29, 34, 0, 2147483647, 10 }, { 29, 22, 0, 842, 24 }, { 29, 47, 0, 2147483647, 81 },
            { 29, 33, 0, 622, 11 }, { 7, 42, 0, 2147483647, 100 }, { 7, 38, 0, 2147483647, 100 },
            { 7, 27, 0, 783, 70 }, { 7, 41, 0, 2147483647, 58 }, { 7, 49, 0, 2147483647, 78 },
            { 7, 26, 0, 322, 16 }, { 8, 37, 0, 10, 39 }, { 8, 31, 0, 10, 100 },
            { 8, 35, 0, 690, 64 }, { 8, 45, 0, 701, 74 }, { 8, 39, 0, 76, 81 },
            { 8, 46, 0, 850, 38 }, { 9, 44, 0, 2147483647, 100 }, { 9, 43, 0, 2147483647, 88 },
            { 9, 46, 0, 2147483647, 7 }, { 9, 42, 0, 420, 35 }, { 9, 21, 0, 2147483647, 73 },
            { 9, 39, 0, 470, 89 }, { 10, 49, 0, 18, 100 }, { 10, 42, 0, 18, 100 },
            { 10, 21, 0, 658, 24 }, { 11, 50, 0, 7, 16 }, { 11, 43, 0, 2147483647, 7 },
            { 11, 31, 0, 720, 76 }, { 11, 32, 0, 2147483647, 93 }, { 12, 43, 0, 2147483647, 46 },
            { 12, 39, 0, 9, 100 }, { 12, 44, 0, 947, 6 }, { 12, 47, 0, 2147483647, 16 },
            { 12, 27, 0, 2147483647, 13 }, { 12, 41, 0, 2147483647, 43 }, { 13, 22, 0, 8, 100 },
            { 13, 38, 0, 2147483647, 13 }, { 13, 48, 0, 2147483647, 47 },
            { 13, 34, 0, 2147483647, 38 }, { 13, 41, 0, 126, 11 }, { 22, 40, 0, 8, 70 },
            { 22, 45, 0, 8, 100 }, { 22, 44, 0, 2147483647, 74 }, { 22, 37, 0, 8, 100 },
            { 22, 27, 0, 2147483647, 92 }, { 14, 45, 0, 19, 22 }, { 14, 42, 0, 19, 83 },
            { 14, 36, 0, 962, 37 }, { 15, 44, 0, 10, 100 }, { 15, 38, 0, 2147483647, 8 },
            { 15, 22, 0, 2147483647, 42 }, { 15, 29, 0, 2147483647, 37 },
            { 16, 33, 0, 2147483647, 100 }, { 16, 42, 0, 2147483647, 58 },
            { 16, 31, 0, 2147483647, 81 }, { 16, 29, 0, 378, 78 }, { 17, 45, 0, 2147483647, 31 },
            { 17, 43, 0, 1, 40 }, { 17, 25, 0, 2147483647, 68 }, { 18, 50, 0, 7, 100 },
            { 18, 45, 0, 2147483647, 100 }, { 19, 28, 0, 13, 100 }, { 19, 45, 0, 387, 9 },
            { 28, 35, 0, 13, 18 }, { 28, 42, 0, 2147483647, 47 }, { 28, 34, 0, 2147483647, 100 },
            { 28, 40, 0, 13, 100 }, { 20, 27, 0, 5, 100 }, { 27, 39, 0, 2147483647, 60 },
            { 27, 38, 0, 2147483647, 100 }, { 27, 47, 0, 5, 24 }, { 27, 32, 0, 2147483647, 6 },
            { 27, 41, 0, 2147483647, 100 }, { 27, 48, 0, 5, 100 }, };
        test(testCase, 9919);
    }

    /**
     * Test case generated with NETGEN generator params: vertices = 50, edges = 150, sources = 20,
     * sinks = 20, supply = 200, min. capacity = 1, max. capacity = 1000, min. cost = 1, max. cost =
     * 100, capacitated = 70%, seed = 684190206
     */
    @Test
    public void testGetMinimumCostFlow15()
    {
        int testCase[][] = new int[][] { { 1, 2795 }, { 2, 756 }, { 3, 1215 }, { 4, 16 },
            { 5, 1955 }, { 6, 334 }, { 7, 716 }, { 8, 1414 }, { 9, 482 }, { 10, 320 }, { 11, 369 },
            { 12, 54 }, { 13, 1485 }, { 14, 563 }, { 15, 1871 }, { 16, 5 }, { 17, 554 }, { 18, 17 },
            { 19, 134 }, { 20, 1582 }, { 21, 2107 }, { 22, 617 }, { 23, 676 }, { 24, 1009 },
            { 25, 1051 }, { 26, 1107 }, { 27, 204 }, { 28, 3026 }, { 29, -122 }, { 30, 1573 },
            { 31, -2153 }, { 32, -2656 }, { 33, -1422 }, { 34, -1605 }, { 35, -1583 },
            { 36, -1066 }, { 37, -1335 }, { 38, -992 }, { 39, -888 }, { 40, -1455 }, { 41, -745 },
            { 42, -1464 }, { 43, -603 }, { 44, -719 }, { 45, -494 }, { 46, -2326 }, { 47, -3254 },
            { 48, -771 }, { 49, -1471 }, { 50, -883 }, { 1, 29, 1, 5, 58 },
            { 1, 32, 764, 2147483647, 98 }, { 1, 22, 455, 2147483647, 100 },
            { 1, 27, 795, 2147483647, 37 }, { 1, 31, 772, 2147483647, 32 }, { 1, 34, 3, 332, 38 },
            { 29, 46, 621, 2147483647, 96 }, { 29, 44, 1, 5, 100 }, { 29, 42, 1, 5, 100 },
            { 29, 35, 1, 5, 100 }, { 29, 26, 1, 275, 1 }, { 2, 30, 740, 2147483647, 28 },
            { 2, 37, 7, 602, 34 }, { 2, 45, 6, 707, 65 }, { 2, 46, 1, 750, 22 },
            { 30, 38, 519, 2147483647, 4 }, { 30, 39, 63, 2147483647, 100 }, { 30, 48, 1, 2, 100 },
            { 30, 45, 484, 2147483647, 81 }, { 30, 29, 746, 2147483647, 46 },
            { 30, 35, 298, 2147483647, 35 }, { 30, 43, 466, 2147483647, 82 },
            { 3, 24, 139, 2147483647, 100 }, { 3, 47, 547, 2147483647, 34 }, { 3, 37, 4, 618, 96 },
            { 3, 42, 506, 2147483647, 77 }, { 3, 44, 2, 306, 71 }, { 3, 48, 5, 550, 76 },
            { 21, 49, 520, 2147483647, 94 }, { 21, 47, 474, 2147483647, 100 },
            { 21, 43, 1, 12, 70 }, { 21, 33, 883, 2147483647, 100 }, { 21, 50, 3, 589, 91 },
            { 21, 44, 267, 2147483647, 74 }, { 21, 30, 264, 2147483647, 54 },
            { 21, 24, 1, 607, 58 }, { 21, 35, 467, 2147483647, 95 }, { 24, 21, 1, 12, 85 },
            { 24, 37, 134, 2147483647, 100 }, { 24, 31, 256, 2147483647, 100 },
            { 24, 34, 508, 2147483647, 100 }, { 24, 50, 841, 2147483647, 13 },
            { 24, 46, 1, 248, 70 }, { 24, 26, 1, 128, 44 }, { 24, 36, 1, 141, 5 },
            { 4, 27, 1, 10, 100 }, { 4, 21, 5, 715, 27 }, { 27, 50, 1, 10, 100 },
            { 27, 47, 901, 2147483647, 100 }, { 27, 35, 1, 10, 73 },
            { 27, 33, 513, 2147483647, 100 }, { 27, 40, 1, 309, 92 },
            { 5, 22, 678, 2147483647, 100 }, { 5, 32, 260, 2147483647, 16 }, { 5, 48, 5, 476, 88 },
            { 5, 46, 500, 2147483647, 96 }, { 5, 31, 498, 2147483647, 46 }, { 5, 49, 3, 495, 83 },
            { 22, 34, 967, 2147483647, 36 }, { 22, 31, 1, 11, 100 }, { 22, 42, 1, 11, 39 },
            { 22, 32, 1, 11, 12 }, { 22, 45, 2, 129, 10 }, { 22, 40, 654, 2147483647, 87 },
            { 22, 26, 7, 856, 7 }, { 22, 35, 149, 2147483647, 14 }, { 6, 28, 310, 2147483647, 100 },
            { 6, 38, 3, 416, 21 }, { 6, 47, 1, 132, 34 }, { 6, 33, 1, 348, 93 },
            { 28, 40, 1, 19, 100 }, { 28, 47, 561, 2147483647, 59 },
            { 28, 36, 514, 2147483647, 100 }, { 28, 37, 859, 2147483647, 100 },
            { 28, 46, 458, 2147483647, 7 }, { 28, 42, 946, 2147483647, 32 },
            { 7, 32, 688, 2147483647, 91 }, { 7, 47, 1, 15, 90 }, { 7, 46, 7, 737, 51 },
            { 7, 33, 3, 746, 74 }, { 7, 25, 2, 977, 18 }, { 8, 38, 1, 4, 80 },
            { 8, 31, 617, 2147483647, 100 }, { 8, 40, 792, 2147483647, 9 },
            { 9, 25, 466, 2147483647, 13 }, { 9, 32, 8, 859, 53 }, { 25, 26, 600, 2147483647, 100 },
            { 25, 43, 1, 8, 100 }, { 25, 32, 1, 8, 100 }, { 25, 39, 823, 2147483647, 59 },
            { 25, 34, 64, 2147483647, 100 }, { 25, 46, 207, 2147483647, 73 },
            { 25, 38, 19, 2147483647, 97 }, { 25, 48, 557, 2147483647, 32 },
            { 25, 50, 33, 2147483647, 66 }, { 26, 48, 63, 2147483647, 83 }, { 26, 37, 1, 8, 100 },
            { 26, 40, 1, 8, 32 }, { 26, 45, 1, 8, 8 }, { 26, 41, 393, 2147483647, 85 },
            { 26, 24, 594, 2147483647, 40 }, { 26, 49, 664, 2147483647, 70 },
            { 10, 48, 131, 2147483647, 100 }, { 10, 44, 178, 2147483647, 36 },
            { 10, 42, 1, 469, 29 }, { 11, 34, 1, 12, 100 }, { 11, 41, 345, 2147483647, 13 },
            { 11, 37, 1, 3, 67 }, { 11, 36, 3, 472, 90 }, { 11, 33, 6, 603, 90 },
            { 11, 26, 1, 41, 10 }, { 12, 33, 1, 13, 7 }, { 12, 34, 36, 2147483647, 100 },
            { 12, 42, 4, 847, 10 }, { 13, 37, 84, 2147483647, 100 },
            { 13, 46, 195, 2147483647, 100 }, { 13, 35, 2, 627, 70 },
            { 13, 27, 417, 2147483647, 9 }, { 13, 47, 753, 2147483647, 12 }, { 14, 23, 1, 17, 64 },
            { 14, 49, 276, 2147483647, 35 }, { 14, 37, 1, 171, 36 },
            { 14, 44, 265, 2147483647, 91 }, { 14, 28, 3, 302, 29 },
            { 23, 37, 207, 2147483647, 100 }, { 23, 46, 303, 2147483647, 100 },
            { 23, 41, 1, 17, 100 }, { 23, 47, 1, 17, 100 }, { 23, 31, 3, 750, 69 },
            { 23, 22, 32, 2147483647, 40 }, { 23, 35, 1, 146, 68 }, { 23, 32, 129, 2147483647, 7 },
            { 15, 42, 1, 2, 36 }, { 15, 38, 440, 2147483647, 67 }, { 15, 21, 767, 2147483647, 59 },
            { 15, 35, 661, 2147483647, 90 }, { 16, 34, 1, 1, 95 }, { 16, 37, 1, 1, 100 },
            { 16, 31, 2, 173, 2 }, { 17, 48, 1, 4, 40 }, { 17, 49, 1, 4, 25 },
            { 17, 46, 6, 563, 92 }, { 17, 36, 542, 2147483647, 20 }, { 18, 33, 1, 15, 100 },
            { 18, 46, 1, 15, 61 }, { 19, 43, 132, 2147483647, 100 }, { 19, 39, 1, 1, 65 },
            { 20, 38, 1, 5, 21 }, { 20, 32, 790, 2147483647, 27 },
            { 20, 25, 786, 2147483647, 47 }, };
        test(testCase, 2223579);
    }

    /**
     * Test case generated with NETGEN generator params: vertices = 100, edges = 704, sources = 25,
     * sinks = 25, supply = 200, min. capacity = 1, max. capacity = 1000, min. cost = 1, max. cost =
     * 20, capacitated = 60%, seed = 1787733798
     */
    @Test
    public void testGetMinimumCostFlow16()
    {
        int testCase[][] = new int[][] { { 1, 4633 }, { 2, 2319 }, { 3, 4198 }, { 4, 5 },
            { 5, 632 }, { 6, 712 }, { 7, 1391 }, { 8, 352 }, { 9, 451 }, { 10, 6187 }, { 11, 387 },
            { 12, 2936 }, { 13, 1989 }, { 14, 498 }, { 15, 903 }, { 16, 1656 }, { 17, 6166 },
            { 18, 3393 }, { 19, 2559 }, { 20, 1753 }, { 21, 493 }, { 22, 1992 }, { 23, 916 },
            { 24, 893 }, { 25, 4075 }, { 26, 1654 }, { 27, 229 }, { 28, -640 }, { 29, -638 },
            { 30, 3403 }, { 31, 65 }, { 32, -842 }, { 33, 2515 }, { 34, -969 }, { 35, 1923 },
            { 36, -914 }, { 37, 542 }, { 38, -162 }, { 39, 865 }, { 40, 2454 }, { 41, 5550 },
            { 42, 1262 }, { 43, -514 }, { 44, -1999 }, { 45, 986 }, { 46, 747 }, { 47, 711 },
            { 48, -1441 }, { 49, -1026 }, { 50, 2577 }, { 51, 61 }, { 52, -1619 }, { 53, -77 },
            { 54, -2799 }, { 55, -701 }, { 56, -7 }, { 57, -587 }, { 58, 664 }, { 59, 561 },
            { 60, -2044 }, { 61, -2047 }, { 62, -544 }, { 63, 3828 }, { 64, 2185 }, { 65, 3753 },
            { 66, -2554 }, { 67, -688 }, { 68, -2502 }, { 69, 2299 }, { 70, -148 }, { 71, -571 },
            { 72, -2946 }, { 73, 4628 }, { 74, 650 }, { 75, -3672 }, { 76, -1979 }, { 77, -3311 },
            { 78, -3750 }, { 79, -1998 }, { 80, -4140 }, { 81, -3882 }, { 82, -2634 },
            { 83, -1567 }, { 84, -2260 }, { 85, -3949 }, { 86, -1264 }, { 87, -2951 },
            { 88, -3001 }, { 89, -1908 }, { 90, -2301 }, { 91, -1186 }, { 92, -3067 },
            { 93, -1904 }, { 94, -4066 }, { 95, -2201 }, { 96, -1848 }, { 97, -1689 },
            { 98, -2234 }, { 99, -1255 }, { 100, -2605 }, { 1, 36, 1, 2, 20 },
            { 1, 93, 522, 2147483647, 13 }, { 1, 88, 1, 239, 16 }, { 1, 81, 789, 2147483647, 10 },
            { 1, 68, 2, 199, 4 }, { 1, 94, 44, 2147483647, 9 }, { 1, 49, 418, 2147483647, 5 },
            { 1, 26, 547, 2147483647, 2 }, { 1, 78, 995, 2147483647, 1 }, { 1, 38, 4, 712, 11 },
            { 1, 32, 660, 2147483647, 18 }, { 1, 43, 1, 367, 9 }, { 1, 75, 353, 2147483647, 8 },
            { 1, 85, 286, 2147483647, 9 }, { 1, 60, 2, 365, 13 }, { 1, 53, 6, 506, 9 },
            { 36, 70, 1, 2, 20 }, { 36, 79, 5, 652, 2 }, { 36, 65, 822, 2147483647, 20 },
            { 36, 74, 5, 496, 8 }, { 36, 83, 5, 553, 9 }, { 36, 50, 8, 806, 16 },
            { 36, 27, 2, 193, 3 }, { 36, 67, 468, 2147483647, 10 }, { 36, 72, 138, 2147483647, 1 },
            { 36, 73, 1, 749, 20 }, { 36, 77, 948, 2147483647, 20 }, { 36, 97, 4, 993, 19 },
            { 70, 98, 177, 2147483647, 19 }, { 70, 88, 1, 2, 13 }, { 70, 34, 459, 2147483647, 18 },
            { 70, 69, 406, 2147483647, 7 }, { 70, 50, 1, 7, 2 }, { 70, 64, 804, 2147483647, 17 },
            { 70, 89, 1, 58, 18 }, { 70, 73, 123, 2147483647, 11 }, { 70, 45, 4, 493, 16 },
            { 70, 38, 6, 711, 17 }, { 2, 44, 1, 3, 17 }, { 2, 74, 400, 2147483647, 10 },
            { 2, 94, 244, 2147483647, 13 }, { 2, 50, 132, 2147483647, 10 },
            { 2, 80, 722, 2147483647, 13 }, { 2, 43, 2, 482, 19 }, { 2, 27, 7, 937, 8 },
            { 2, 77, 780, 2147483647, 1 }, { 2, 90, 3, 283, 14 }, { 2, 59, 5, 444, 12 },
            { 2, 86, 7, 678, 14 }, { 2, 42, 5, 590, 11 }, { 2, 31, 6, 518, 7 },
            { 2, 34, 2, 218, 3 }, { 40, 50, 1, 3, 20 }, { 40, 77, 4, 391, 9 },
            { 40, 87, 737, 2147483647, 3 }, { 40, 65, 563, 2147483647, 18 },
            { 40, 64, 762, 2147483647, 19 }, { 40, 100, 2, 812, 11 },
            { 40, 97, 263, 2147483647, 16 }, { 40, 96, 242, 2147483647, 17 },
            { 40, 61, 1, 323, 10 }, { 40, 36, 731, 2147483647, 8 }, { 44, 40, 1, 3, 5 },
            { 44, 28, 626, 2147483647, 11 }, { 50, 88, 58, 2147483647, 3 },
            { 50, 93, 501, 2147483647, 20 }, { 50, 96, 225, 2147483647, 20 }, { 50, 85, 1, 498, 6 },
            { 50, 73, 735, 2147483647, 10 }, { 50, 30, 108, 2147483647, 2 }, { 50, 56, 8, 718, 2 },
            { 50, 68, 512, 2147483647, 16 }, { 50, 71, 5, 742, 17 }, { 50, 51, 714, 2147483647, 7 },
            { 50, 100, 607, 2147483647, 13 }, { 50, 83, 789, 2147483647, 14 },
            { 50, 26, 3, 980, 10 }, { 50, 99, 1, 91, 15 }, { 50, 53, 6, 652, 11 },
            { 50, 91, 186, 2147483647, 18 }, { 3, 35, 1, 2, 16 }, { 3, 44, 188, 2147483647, 8 },
            { 3, 81, 996, 2147483647, 13 }, { 3, 61, 3, 700, 9 }, { 3, 67, 1, 19, 1 },
            { 3, 60, 3, 583, 9 }, { 3, 82, 2, 627, 5 }, { 3, 66, 962, 2147483647, 12 },
            { 3, 79, 4, 668, 10 }, { 3, 72, 426, 2147483647, 20 }, { 3, 76, 937, 2147483647, 2 },
            { 3, 97, 4, 417, 14 }, { 3, 47, 5, 490, 19 }, { 3, 34, 663, 2147483647, 17 },
            { 3, 36, 1, 88, 13 }, { 35, 47, 1, 2, 20 }, { 35, 91, 529, 2147483647, 20 },
            { 35, 76, 348, 2147483647, 18 }, { 35, 99, 5, 691, 18 },
            { 35, 100, 614, 2147483647, 10 }, { 35, 65, 246, 2147483647, 5 },
            { 35, 26, 626, 2147483647, 16 }, { 35, 81, 7, 660, 1 }, { 35, 39, 3, 530, 13 },
            { 35, 97, 411, 2147483647, 9 }, { 35, 50, 545, 2147483647, 7 },
            { 35, 49, 248, 2147483647, 13 }, { 35, 98, 663, 2147483647, 4 },
            { 47, 66, 883, 2147483647, 20 }, { 47, 91, 1, 34, 16 }, { 47, 68, 969, 2147483647, 10 },
            { 47, 59, 964, 2147483647, 16 }, { 47, 95, 481, 2147483647, 6 },
            { 47, 62, 211, 2147483647, 9 }, { 66, 88, 424, 2147483647, 5 }, { 66, 93, 1, 2, 6 },
            { 66, 26, 7, 696, 2 }, { 66, 76, 2, 473, 14 }, { 66, 39, 4, 691, 3 },
            { 4, 26, 1, 3, 19 }, { 4, 47, 1, 533, 5 }, { 26, 57, 980, 2147483647, 7 },
            { 26, 70, 1, 61, 17 }, { 26, 76, 1, 163, 12 }, { 26, 28, 185, 2147483647, 1 },
            { 26, 31, 11, 2147483647, 11 }, { 26, 41, 3, 272, 18 }, { 26, 43, 5, 945, 11 },
            { 26, 35, 1, 55, 9 }, { 26, 90, 659, 2147483647, 9 }, { 26, 93, 1, 97, 16 },
            { 26, 55, 319, 2147483647, 7 }, { 26, 61, 961, 2147483647, 1 },
            { 26, 51, 115, 2147483647, 16 }, { 26, 84, 4, 388, 2 }, { 57, 94, 291, 2147483647, 17 },
            { 57, 97, 117, 2147483647, 20 }, { 57, 42, 52, 2147483647, 10 },
            { 57, 83, 136, 2147483647, 5 }, { 57, 65, 6, 539, 13 }, { 57, 95, 2, 143, 3 },
            { 57, 68, 905, 2147483647, 13 }, { 57, 64, 726, 2147483647, 8 },
            { 57, 34, 688, 2147483647, 5 }, { 57, 59, 1, 232, 13 }, { 57, 70, 615, 2147483647, 20 },
            { 5, 34, 1, 11, 17 }, { 5, 91, 1, 418, 20 }, { 5, 86, 1, 6, 20 }, { 5, 80, 1, 82, 11 },
            { 5, 87, 3, 515, 11 }, { 5, 43, 2, 279, 18 }, { 5, 81, 370, 2147483647, 8 },
            { 5, 30, 5, 810, 15 }, { 5, 48, 2, 140, 18 }, { 5, 64, 1, 199, 18 },
            { 5, 65, 6, 757, 11 }, { 5, 94, 228, 2147483647, 17 }, { 34, 55, 121, 2147483647, 10 },
            { 34, 81, 1, 11, 18 }, { 34, 35, 961, 2147483647, 7 }, { 34, 41, 211, 2147483647, 13 },
            { 34, 82, 4, 973, 3 }, { 34, 26, 2, 901, 16 }, { 34, 44, 179, 2147483647, 3 },
            { 55, 78, 85, 2147483647, 20 }, { 55, 81, 5, 883, 8 }, { 55, 34, 3, 390, 6 },
            { 55, 33, 1, 311, 20 }, { 55, 85, 1, 186, 15 }, { 55, 93, 6, 574, 1 },
            { 55, 46, 978, 2147483647, 14 }, { 55, 72, 231, 2147483647, 6 },
            { 6, 72, 143, 2147483647, 12 }, { 6, 46, 5, 886, 14 }, { 6, 32, 7, 664, 9 },
            { 6, 36, 278, 2147483647, 5 }, { 6, 47, 277, 2147483647, 1 },
            { 33, 80, 692, 2147483647, 20 }, { 33, 81, 51, 2147483647, 20 }, { 33, 88, 1, 92, 10 },
            { 33, 93, 466, 2147483647, 13 }, { 33, 60, 877, 2147483647, 4 },
            { 33, 41, 54, 2147483647, 5 }, { 33, 67, 235, 2147483647, 5 },
            { 33, 38, 72, 2147483647, 9 }, { 33, 94, 2, 137, 1 }, { 33, 34, 8, 722, 2 },
            { 33, 65, 1, 131, 16 }, { 33, 27, 1, 348, 17 }, { 33, 57, 480, 2147483647, 4 },
            { 33, 100, 810, 2147483647, 2 }, { 33, 62, 485, 2147483647, 5 }, { 33, 55, 8, 937, 11 },
            { 33, 90, 1, 612, 5 }, { 72, 33, 1, 2, 20 }, { 72, 62, 2, 253, 5 },
            { 72, 52, 2, 107, 3 }, { 72, 71, 88, 2147483647, 5 }, { 7, 65, 1, 8, 8 },
            { 7, 85, 439, 2147483647, 11 }, { 7, 47, 9, 950, 1 }, { 7, 63, 204, 2147483647, 15 },
            { 7, 78, 729, 2147483647, 18 }, { 7, 37, 1, 927, 6 }, { 30, 94, 597, 2147483647, 20 },
            { 30, 59, 5, 538, 17 }, { 30, 55, 808, 2147483647, 1 }, { 30, 43, 3, 677, 2 },
            { 30, 83, 442, 2147483647, 15 }, { 30, 26, 46, 2147483647, 3 },
            { 30, 68, 718, 2147483647, 11 }, { 30, 92, 954, 2147483647, 3 }, { 30, 62, 1, 131, 15 },
            { 30, 78, 406, 2147483647, 10 }, { 30, 44, 4, 703, 1 }, { 30, 75, 246, 2147483647, 2 },
            { 30, 38, 829, 2147483647, 6 }, { 30, 85, 1, 323, 2 }, { 30, 98, 399, 2147483647, 4 },
            { 52, 30, 1, 8, 16 }, { 52, 88, 1, 8, 20 }, { 52, 73, 1, 22, 11 },
            { 52, 46, 2, 187, 10 }, { 52, 78, 219, 2147483647, 4 }, { 52, 48, 4, 565, 20 },
            { 65, 68, 272, 2147483647, 20 }, { 65, 100, 437, 2147483647, 9 },
            { 65, 98, 689, 2147483647, 6 }, { 65, 97, 2, 243, 6 }, { 65, 95, 843, 2147483647, 5 },
            { 65, 69, 10, 981, 10 }, { 65, 49, 393, 2147483647, 10 },
            { 65, 81, 168, 2147483647, 14 }, { 65, 29, 1, 451, 7 }, { 65, 57, 999, 2147483647, 10 },
            { 65, 71, 1, 68, 13 }, { 65, 51, 1, 126, 2 }, { 65, 82, 592, 2147483647, 2 },
            { 65, 90, 484, 2147483647, 1 }, { 65, 28, 1, 85, 16 }, { 65, 77, 926, 2147483647, 5 },
            { 65, 56, 378, 2147483647, 8 }, { 68, 52, 1, 8, 20 }, { 68, 56, 4, 962, 1 },
            { 68, 54, 580, 2147483647, 17 }, { 68, 32, 1, 192, 15 },
            { 68, 67, 658, 2147483647, 17 }, { 68, 44, 945, 2147483647, 2 }, { 68, 87, 1, 88, 3 },
            { 68, 38, 473, 2147483647, 6 }, { 8, 67, 273, 2147483647, 3 }, { 8, 29, 7, 946, 12 },
            { 8, 88, 57, 2147483647, 20 }, { 8, 80, 3, 284, 5 }, { 8, 59, 4, 714, 2 },
            { 54, 88, 495, 2147483647, 7 }, { 54, 60, 2, 999, 4 }, { 54, 58, 822, 2147483647, 17 },
            { 54, 70, 544, 2147483647, 18 }, { 67, 54, 951, 2147483647, 20 },
            { 67, 79, 531, 2147483647, 20 }, { 67, 39, 3, 926, 16 }, { 67, 99, 1, 251, 17 },
            { 67, 81, 4, 884, 12 }, { 67, 84, 5, 746, 4 }, { 67, 41, 4, 473, 17 },
            { 9, 73, 1, 10, 17 }, { 9, 50, 1, 26, 1 }, { 9, 36, 2, 101, 9 },
            { 9, 62, 181, 2147483647, 14 }, { 9, 35, 1, 855, 1 }, { 9, 78, 2, 734, 5 },
            { 9, 40, 247, 2147483647, 11 }, { 9, 27, 1, 3, 18 }, { 9, 86, 5, 408, 14 },
            { 71, 97, 686, 2147483647, 6 }, { 71, 100, 2, 734, 13 }, { 71, 61, 736, 2147483647, 4 },
            { 71, 82, 1, 189, 20 }, { 71, 44, 5, 484, 3 }, { 71, 34, 1, 117, 12 },
            { 73, 71, 815, 2147483647, 20 }, { 73, 85, 738, 2147483647, 12 },
            { 73, 72, 4, 353, 10 }, { 73, 92, 3, 508, 13 }, { 73, 74, 175, 2147483647, 19 },
            { 73, 79, 1, 888, 1 }, { 73, 48, 366, 2147483647, 13 }, { 73, 31, 6, 958, 10 },
            { 73, 61, 1, 427, 11 }, { 73, 58, 781, 2147483647, 12 },
            { 73, 36, 456, 2147483647, 16 }, { 73, 49, 650, 2147483647, 19 },
            { 73, 54, 140, 2147483647, 10 }, { 73, 55, 130, 2147483647, 14 },
            { 73, 38, 10, 988, 8 }, { 73, 47, 774, 2147483647, 12 }, { 73, 26, 5, 530, 12 },
            { 73, 86, 807, 2147483647, 16 }, { 10, 60, 1, 12, 20 }, { 10, 85, 389, 2147483647, 1 },
            { 10, 34, 177, 2147483647, 11 }, { 10, 69, 576, 2147483647, 14 }, { 10, 49, 5, 751, 2 },
            { 10, 28, 7, 811, 1 }, { 10, 33, 479, 2147483647, 20 }, { 10, 51, 2, 449, 8 },
            { 10, 89, 638, 2147483647, 5 }, { 10, 42, 831, 2147483647, 14 },
            { 10, 87, 564, 2147483647, 19 }, { 10, 75, 918, 2147483647, 1 }, { 10, 29, 1, 336, 6 },
            { 10, 48, 894, 2147483647, 10 }, { 10, 70, 3, 308, 3 }, { 10, 81, 690, 2147483647, 15 },
            { 37, 96, 236, 2147483647, 20 }, { 37, 84, 224, 2147483647, 20 },
            { 37, 60, 349, 2147483647, 19 }, { 37, 100, 127, 2147483647, 18 },
            { 37, 68, 7, 897, 18 }, { 37, 54, 3, 391, 9 }, { 60, 37, 1, 12, 6 },
            { 60, 55, 1, 108, 1 }, { 60, 95, 3, 970, 17 }, { 60, 56, 1, 85, 9 },
            { 60, 27, 856, 2147483647, 8 }, { 60, 43, 3, 553, 2 }, { 60, 62, 1, 641, 12 },
            { 60, 28, 2, 319, 8 }, { 60, 30, 2, 937, 13 }, { 60, 59, 1, 89, 14 },
            { 11, 49, 1, 10, 20 }, { 11, 99, 2, 835, 1 }, { 11, 32, 9, 956, 9 },
            { 11, 33, 365, 2147483647, 1 }, { 32, 92, 1, 10, 20 }, { 32, 84, 151, 2147483647, 20 },
            { 32, 40, 591, 2147483647, 6 }, { 32, 90, 1, 193, 3 }, { 32, 99, 1, 202, 3 },
            { 32, 60, 835, 2147483647, 11 }, { 32, 34, 4, 458, 16 }, { 49, 32, 1, 10, 15 },
            { 49, 47, 192, 2147483647, 18 }, { 49, 54, 604, 2147483647, 11 },
            { 12, 51, 49, 2147483647, 14 }, { 12, 71, 292, 2147483647, 11 },
            { 12, 61, 423, 2147483647, 1 }, { 12, 86, 331, 2147483647, 11 },
            { 12, 68, 851, 2147483647, 6 }, { 12, 83, 3, 308, 16 }, { 12, 80, 967, 2147483647, 18 },
            { 12, 31, 1, 323, 17 }, { 12, 62, 3, 933, 14 }, { 12, 97, 3, 236, 13 },
            { 12, 37, 3, 861, 3 }, { 51, 92, 1, 10, 5 }, { 51, 94, 905, 2147483647, 20 },
            { 51, 86, 5, 564, 5 }, { 51, 77, 297, 2147483647, 4 }, { 51, 60, 1, 104, 11 },
            { 51, 30, 1, 24, 12 }, { 51, 52, 739, 2147483647, 4 }, { 51, 45, 4, 707, 20 },
            { 51, 85, 246, 2147483647, 14 }, { 51, 54, 479, 2147483647, 5 },
            { 51, 29, 162, 2147483647, 2 }, { 51, 47, 742, 2147483647, 5 }, { 51, 35, 7, 667, 7 },
            { 13, 43, 954, 2147483647, 5 }, { 13, 59, 1, 994, 17 }, { 13, 93, 7, 985, 10 },
            { 13, 95, 128, 2147483647, 4 }, { 13, 87, 893, 2147483647, 8 },
            { 43, 89, 712, 2147483647, 20 }, { 43, 94, 462, 2147483647, 4 },
            { 43, 72, 10, 973, 19 }, { 43, 30, 200, 2147483647, 10 }, { 43, 44, 1, 532, 14 },
            { 43, 73, 1, 727, 16 }, { 43, 65, 5, 811, 12 }, { 14, 58, 1, 7, 20 },
            { 14, 84, 487, 2147483647, 15 }, { 14, 90, 3, 267, 18 }, { 41, 81, 60, 2147483647, 11 },
            { 41, 62, 479, 2147483647, 4 }, { 41, 27, 2, 111, 3 }, { 41, 63, 750, 2147483647, 6 },
            { 41, 46, 5, 604, 6 }, { 41, 57, 610, 2147483647, 16 }, { 41, 69, 863, 2147483647, 14 },
            { 41, 34, 3, 398, 16 }, { 41, 70, 962, 2147483647, 6 }, { 41, 71, 801, 2147483647, 15 },
            { 41, 75, 715, 2147483647, 18 }, { 41, 55, 615, 2147483647, 9 }, { 41, 42, 3, 330, 10 },
            { 58, 41, 46, 2147483647, 20 }, { 58, 98, 85, 2147483647, 20 },
            { 58, 26, 337, 2147483647, 19 }, { 58, 38, 701, 2147483647, 2 },
            { 58, 54, 943, 2147483647, 18 }, { 58, 60, 3, 217, 15 }, { 58, 78, 71, 2147483647, 20 },
            { 58, 48, 211, 2147483647, 6 }, { 58, 32, 359, 2147483647, 10 },
            { 15, 28, 890, 2147483647, 20 }, { 15, 38, 6, 769, 20 },
            { 28, 53, 548, 2147483647, 16 }, { 28, 76, 1, 7, 20 }, { 28, 46, 4, 399, 14 },
            { 28, 32, 1, 485, 16 }, { 28, 60, 2, 495, 20 }, { 28, 92, 693, 2147483647, 1 },
            { 28, 94, 1, 90, 17 }, { 53, 88, 639, 2147483647, 4 }, { 53, 73, 146, 2147483647, 5 },
            { 53, 47, 1, 44, 3 }, { 53, 49, 7, 892, 16 }, { 16, 56, 1, 9, 20 },
            { 16, 55, 2, 294, 20 }, { 16, 74, 1, 189, 12 }, { 16, 26, 8, 771, 1 },
            { 16, 76, 4, 506, 9 }, { 16, 48, 337, 2147483647, 20 }, { 16, 51, 2, 223, 9 },
            { 16, 59, 919, 2147483647, 10 }, { 16, 46, 372, 2147483647, 7 }, { 16, 82, 1, 233, 5 },
            { 56, 83, 1, 9, 15 }, { 56, 80, 823, 2147483647, 20 }, { 56, 55, 7, 697, 3 },
            { 56, 84, 412, 2147483647, 7 }, { 17, 27, 841, 2147483647, 20 },
            { 17, 64, 994, 2147483647, 7 }, { 17, 85, 989, 2147483647, 12 }, { 17, 46, 7, 640, 12 },
            { 17, 44, 810, 2147483647, 2 }, { 17, 29, 963, 2147483647, 13 }, { 17, 30, 2, 221, 16 },
            { 17, 74, 43, 2147483647, 7 }, { 17, 83, 173, 2147483647, 14 },
            { 17, 42, 339, 2147483647, 1 }, { 17, 93, 200, 2147483647, 12 }, { 17, 45, 1, 94, 5 },
            { 17, 47, 792, 2147483647, 8 }, { 27, 46, 57, 2147483647, 17 }, { 27, 83, 7, 671, 10 },
            { 27, 56, 849, 2147483647, 11 }, { 27, 53, 2, 234, 10 }, { 27, 69, 357, 2147483647, 5 },
            { 27, 87, 2, 166, 4 }, { 27, 88, 20, 2147483647, 1 }, { 27, 66, 1, 319, 7 },
            { 27, 34, 4, 568, 1 }, { 27, 72, 966, 2147483647, 3 }, { 27, 42, 241, 2147483647, 8 },
            { 27, 94, 1, 608, 12 }, { 27, 26, 4, 489, 10 }, { 46, 77, 1, 12, 20 },
            { 46, 96, 1, 12, 20 }, { 46, 34, 1, 174, 3 }, { 46, 31, 681, 2147483647, 17 },
            { 46, 92, 540, 2147483647, 15 }, { 46, 85, 808, 2147483647, 14 },
            { 46, 32, 6, 505, 10 }, { 46, 38, 242, 2147483647, 9 }, { 46, 66, 332, 2147483647, 7 },
            { 18, 63, 1, 14, 20 }, { 18, 75, 704, 2147483647, 1 }, { 18, 96, 1, 22, 6 },
            { 18, 66, 1, 349, 1 }, { 18, 43, 925, 2147483647, 19 }, { 18, 64, 537, 2147483647, 10 },
            { 18, 62, 875, 2147483647, 16 }, { 18, 45, 328, 2147483647, 5 }, { 18, 48, 6, 647, 17 },
            { 18, 30, 1, 315, 2 }, { 38, 82, 1, 14, 19 }, { 38, 32, 667, 2147483647, 5 },
            { 38, 72, 978, 2147483647, 15 }, { 38, 57, 1, 378, 16 }, { 38, 80, 4, 482, 10 },
            { 38, 44, 8, 800, 1 }, { 38, 46, 2, 105, 4 }, { 38, 58, 487, 2147483647, 13 },
            { 38, 74, 4, 392, 3 }, { 38, 98, 4, 763, 20 }, { 38, 31, 630, 2147483647, 1 },
            { 63, 74, 682, 2147483647, 20 }, { 63, 89, 410, 2147483647, 18 }, { 63, 31, 1, 99, 1 },
            { 63, 37, 1, 149, 20 }, { 63, 29, 742, 2147483647, 13 },
            { 63, 64, 827, 2147483647, 16 }, { 63, 43, 1, 377, 12 }, { 63, 90, 824, 2147483647, 1 },
            { 63, 35, 900, 2147483647, 12 }, { 63, 61, 645, 2147483647, 10 }, { 63, 46, 1, 36, 1 },
            { 63, 53, 308, 2147483647, 1 }, { 74, 38, 1, 14, 20 }, { 74, 84, 1, 14, 12 },
            { 74, 85, 1, 14, 20 }, { 74, 62, 3, 795, 6 }, { 74, 37, 397, 2147483647, 8 },
            { 74, 98, 191, 2147483647, 8 }, { 74, 28, 179, 2147483647, 15 },
            { 74, 94, 343, 2147483647, 20 }, { 74, 92, 838, 2147483647, 1 }, { 74, 93, 5, 442, 3 },
            { 74, 40, 5, 522, 12 }, { 19, 29, 1, 11, 20 }, { 19, 69, 646, 2147483647, 3 },
            { 19, 57, 233, 2147483647, 15 }, { 19, 34, 431, 2147483647, 3 },
            { 19, 51, 680, 2147483647, 19 }, { 19, 59, 1, 133, 7 }, { 19, 62, 3, 356, 10 },
            { 19, 52, 553, 2147483647, 12 }, { 29, 39, 1, 11, 10 }, { 29, 87, 1, 11, 20 },
            { 29, 64, 3, 451, 20 }, { 29, 92, 28, 2147483647, 13 }, { 29, 60, 397, 2147483647, 6 },
            { 29, 30, 3, 701, 13 }, { 29, 40, 8, 812, 13 }, { 29, 52, 211, 2147483647, 19 },
            { 29, 26, 3, 380, 3 }, { 29, 98, 19, 2147483647, 7 }, { 29, 100, 3, 366, 7 },
            { 29, 49, 4, 643, 1 }, { 29, 85, 1, 180, 4 }, { 29, 51, 917, 2147483647, 2 },
            { 29, 75, 2, 959, 4 }, { 29, 82, 1, 20, 8 }, { 29, 44, 483, 2147483647, 2 },
            { 29, 72, 1, 290, 7 }, { 39, 82, 856, 2147483647, 19 }, { 39, 38, 6, 987, 9 },
            { 39, 56, 3, 564, 11 }, { 39, 98, 1, 233, 14 }, { 39, 76, 6, 2147483647, 20 },
            { 39, 88, 5, 542, 13 }, { 20, 75, 805, 2147483647, 6 }, { 20, 89, 138, 2147483647, 15 },
            { 20, 65, 785, 2147483647, 2 }, { 20, 70, 1, 88, 15 }, { 20, 59, 6, 512, 17 },
            { 20, 34, 1, 120, 11 }, { 20, 90, 8, 809, 6 }, { 20, 50, 1, 345, 12 },
            { 48, 88, 178, 2147483647, 20 }, { 48, 97, 195, 2147483647, 15 },
            { 48, 45, 4, 931, 17 }, { 48, 96, 3, 237, 20 }, { 69, 48, 1, 8, 20 },
            { 69, 82, 2, 580, 15 }, { 69, 34, 2, 444, 15 }, { 69, 88, 719, 2147483647, 16 },
            { 69, 36, 521, 2147483647, 15 }, { 69, 75, 475, 2147483647, 13 },
            { 69, 50, 821, 2147483647, 3 }, { 69, 73, 1, 285, 14 }, { 69, 58, 1, 4, 19 },
            { 69, 93, 191, 2147483647, 11 }, { 69, 78, 561, 2147483647, 7 },
            { 69, 32, 715, 2147483647, 17 }, { 69, 27, 568, 2147483647, 15 },
            { 69, 56, 2, 353, 13 }, { 69, 30, 798, 2147483647, 6 }, { 75, 69, 46, 2147483647, 8 },
            { 75, 99, 367, 2147483647, 20 }, { 75, 93, 1, 8, 5 }, { 75, 96, 895, 2147483647, 13 },
            { 75, 77, 4, 617, 16 }, { 75, 27, 1, 302, 11 }, { 75, 50, 1, 990, 10 },
            { 75, 73, 99, 2147483647, 15 }, { 75, 51, 336, 2147483647, 10 }, { 75, 62, 7, 967, 9 },
            { 75, 90, 1, 980, 12 }, { 75, 42, 1, 69, 5 }, { 75, 52, 1, 102, 11 },
            { 75, 35, 9, 2147483647, 4 }, { 75, 60, 443, 2147483647, 7 },
            { 21, 31, 129, 2147483647, 20 }, { 21, 69, 1, 768, 7 }, { 21, 96, 4, 359, 9 },
            { 21, 75, 351, 2147483647, 6 }, { 31, 45, 1, 8, 1 }, { 31, 83, 1, 8, 5 },
            { 31, 29, 844, 2147483647, 18 }, { 31, 52, 5, 794, 14 }, { 31, 89, 1, 845, 8 },
            { 31, 33, 1, 403, 7 }, { 31, 70, 3, 993, 4 }, { 31, 76, 674, 2147483647, 6 },
            { 45, 99, 494, 2147483647, 20 }, { 45, 47, 2, 523, 11 }, { 45, 57, 823, 2147483647, 4 },
            { 45, 80, 6, 571, 2 }, { 45, 73, 6, 903, 20 }, { 22, 62, 754, 2147483647, 19 },
            { 22, 43, 3, 559, 6 }, { 22, 51, 3, 349, 7 }, { 22, 86, 7, 654, 14 },
            { 22, 54, 9, 842, 14 }, { 22, 56, 4, 777, 20 }, { 22, 78, 507, 2147483647, 17 },
            { 22, 79, 697, 2147483647, 19 }, { 22, 27, 3, 222, 4 }, { 62, 99, 363, 2147483647, 4 },
            { 62, 89, 1, 5, 20 }, { 62, 39, 1, 118, 18 }, { 62, 69, 174, 2147483647, 14 },
            { 62, 66, 14, 2147483647, 2 }, { 62, 78, 149, 2147483647, 18 },
            { 62, 75, 647, 2147483647, 13 }, { 62, 95, 4, 332, 11 }, { 62, 74, 2, 434, 15 },
            { 62, 52, 330, 2147483647, 6 }, { 62, 33, 717, 2147483647, 7 }, { 62, 45, 3, 414, 1 },
            { 62, 29, 1, 34, 9 }, { 62, 50, 370, 2147483647, 15 }, { 62, 65, 7, 778, 3 },
            { 62, 88, 6, 796, 4 }, { 62, 36, 849, 2147483647, 10 }, { 62, 86, 98, 2147483647, 5 },
            { 62, 90, 2, 990, 17 }, { 23, 42, 471, 2147483647, 5 }, { 23, 46, 432, 2147483647, 16 },
            { 42, 64, 609, 2147483647, 20 }, { 42, 50, 1, 738, 4 }, { 42, 76, 3, 259, 16 },
            { 42, 80, 917, 2147483647, 4 }, { 42, 78, 8, 981, 7 }, { 42, 81, 733, 2147483647, 20 },
            { 42, 35, 443, 2147483647, 2 }, { 42, 88, 5, 770, 17 }, { 42, 44, 2, 817, 3 },
            { 42, 100, 1, 173, 20 }, { 42, 52, 5, 733, 17 }, { 42, 73, 120, 2147483647, 17 },
            { 42, 62, 358, 2147483647, 15 }, { 64, 96, 221, 2147483647, 6 },
            { 64, 85, 32, 2147483647, 18 }, { 64, 82, 667, 2147483647, 18 },
            { 64, 54, 953, 2147483647, 7 }, { 64, 43, 3, 389, 4 }, { 64, 79, 756, 2147483647, 12 },
            { 64, 62, 808, 2147483647, 7 }, { 64, 87, 742, 2147483647, 18 },
            { 64, 63, 553, 2147483647, 20 }, { 64, 61, 1, 28, 13 }, { 64, 77, 345, 2147483647, 17 },
            { 64, 67, 552, 2147483647, 7 }, { 64, 30, 935, 2147483647, 19 }, { 64, 78, 5, 693, 1 },
            { 64, 94, 108, 2147483647, 7 }, { 64, 75, 668, 2147483647, 17 },
            { 64, 49, 97, 2147483647, 16 }, { 64, 74, 2, 955, 11 }, { 24, 59, 881, 2147483647, 20 },
            { 24, 80, 2, 343, 20 }, { 24, 38, 1, 263, 15 }, { 24, 43, 1, 139, 1 },
            { 59, 94, 823, 2147483647, 20 }, { 59, 78, 1, 8, 13 }, { 59, 95, 738, 2147483647, 18 },
            { 59, 84, 957, 2147483647, 10 }, { 59, 90, 313, 2147483647, 18 }, { 59, 76, 1, 16, 20 },
            { 59, 65, 2, 123, 20 }, { 59, 72, 142, 2147483647, 19 }, { 59, 43, 2, 284, 18 },
            { 59, 88, 372, 2147483647, 6 }, { 25, 61, 245, 2147483647, 20 }, { 25, 94, 1, 143, 8 },
            { 25, 47, 2, 179, 2 }, { 25, 66, 799, 2147483647, 7 }, { 25, 99, 4, 745, 14 },
            { 25, 36, 482, 2147483647, 19 }, { 25, 59, 2, 609, 15 }, { 25, 37, 1, 981, 1 },
            { 25, 29, 2, 947, 20 }, { 25, 98, 1, 534, 5 }, { 25, 33, 165, 2147483647, 17 },
            { 25, 38, 597, 2147483647, 14 }, { 25, 84, 4, 903, 10 }, { 25, 26, 3, 425, 8 },
            { 25, 63, 6, 854, 9 }, { 25, 86, 1, 40, 14 }, { 25, 62, 111, 2147483647, 4 },
            { 25, 51, 709, 2147483647, 8 }, { 25, 68, 929, 2147483647, 15 }, { 61, 99, 1, 11, 20 },
            { 61, 82, 497, 2147483647, 20 }, { 61, 86, 1, 11, 19 }, { 61, 90, 1, 11, 17 },
            { 61, 91, 468, 2147483647, 20 }, { 61, 95, 1, 11, 20 }, };
        test(testCase, 2000171);
    }

    /**
     * Test case generated with NETGEN generator params: vertices = 200, edges = 1501, sources = 50,
     * sinks = 50, supply = 1000, min. capacity = 1, max. capacity = 10000, min. cost = 1, max. cost
     * = 20, capacitated = 60%, seed = 346867034
     */
    @Test
    public void testGetMinimumCostFlow17()
    {
        int testCase[][] = new int[][] { { 1, 2474 }, { 2, 2676 }, { 3, 4366 }, { 4, 7126 },
            { 5, 1006 }, { 6, 3683 }, { 7, 3081 }, { 8, 2395 }, { 9, 3372 }, { 10, 2421 },
            { 11, 3762 }, { 12, 2197 }, { 13, 4288 }, { 14, 1488 }, { 15, 1118 }, { 16, 1746 },
            { 17, 3126 }, { 18, 274 }, { 19, 5439 }, { 20, 2759 }, { 21, 3886 }, { 22, 4610 },
            { 23, 4486 }, { 24, 4541 }, { 25, 258 }, { 26, 3060 }, { 27, 1463 }, { 28, 1104 },
            { 29, 4864 }, { 30, 4064 }, { 31, 4473 }, { 32, 660 }, { 33, 4348 }, { 34, 2836 },
            { 35, 278 }, { 36, 1378 }, { 37, 3872 }, { 38, 3898 }, { 39, 4266 }, { 40, 5751 },
            { 41, 1487 }, { 42, 2000 }, { 43, 668 }, { 44, 1823 }, { 45, 1497 }, { 46, 3331 },
            { 47, 1151 }, { 48, 1156 }, { 49, 352 }, { 50, 1182 }, { 51, 2178 }, { 52, 2579 },
            { 53, -1866 }, { 54, 1631 }, { 55, -6605 }, { 56, -3179 }, { 57, 2881 }, { 58, 578 },
            { 59, -202 }, { 60, 1498 }, { 61, -2284 }, { 62, 1422 }, { 63, -2874 }, { 64, -324 },
            { 65, -3346 }, { 66, -1163 }, { 67, 3478 }, { 68, 1706 }, { 69, 1498 }, { 70, -1594 },
            { 71, 1661 }, { 72, 622 }, { 73, 1964 }, { 74, 4598 }, { 75, -1219 }, { 76, -392 },
            { 77, 2143 }, { 78, -136 }, { 79, -1163 }, { 80, -258 }, { 81, 280 }, { 82, -593 },
            { 83, 374 }, { 84, 4827 }, { 85, 1525 }, { 86, 2228 }, { 87, -1658 }, { 88, 665 },
            { 89, -747 }, { 90, 319 }, { 91, 1756 }, { 92, -1102 }, { 93, -2325 }, { 94, 1019 },
            { 95, -615 }, { 96, -1498 }, { 97, -1243 }, { 98, -7595 }, { 99, -2666 }, { 100, 4033 },
            { 101, 1187 }, { 102, -455 }, { 103, 311 }, { 104, 2524 }, { 105, 1715 },
            { 106, -1564 }, { 107, 5167 }, { 108, 2981 }, { 109, -417 }, { 110, -1970 },
            { 111, -1433 }, { 112, -1451 }, { 113, -2119 }, { 114, -1487 }, { 115, -1875 },
            { 116, 3505 }, { 117, -1 }, { 118, 5867 }, { 119, 3397 }, { 120, 2343 }, { 121, 879 },
            { 122, -646 }, { 123, -1691 }, { 124, -932 }, { 125, 2598 }, { 126, -2181 },
            { 127, -1849 }, { 128, 436 }, { 129, 1910 }, { 130, 2348 }, { 131, 52 }, { 132, 364 },
            { 133, -1614 }, { 134, -1052 }, { 135, 246 }, { 136, -2268 }, { 137, 1424 },
            { 138, 4244 }, { 139, -7281 }, { 140, 1049 }, { 141, 5552 }, { 142, -1973 },
            { 143, -149 }, { 144, 2718 }, { 145, -2921 }, { 146, -266 }, { 147, 1923 },
            { 148, -1842 }, { 149, 2166 }, { 150, 3504 }, { 151, -1797 }, { 152, -1843 },
            { 153, -6399 }, { 154, -1446 }, { 155, -4597 }, { 156, -3660 }, { 157, -3563 },
            { 158, -3779 }, { 159, -4092 }, { 160, -2963 }, { 161, -3012 }, { 162, -3504 },
            { 163, -2791 }, { 164, -1642 }, { 165, -2578 }, { 166, -1710 }, { 167, -1384 },
            { 168, -2428 }, { 169, -2210 }, { 170, -2063 }, { 171, -3516 }, { 172, -2489 },
            { 173, -839 }, { 174, -1605 }, { 175, -3353 }, { 176, -2262 }, { 177, -2566 },
            { 178, -2817 }, { 179, -5543 }, { 180, -3416 }, { 181, -3615 }, { 182, -2276 },
            { 183, -5069 }, { 184, -862 }, { 185, -4166 }, { 186, -1949 }, { 187, -5121 },
            { 188, -3488 }, { 189, -4123 }, { 190, -5798 }, { 191, -6077 }, { 192, -4953 },
            { 193, -1826 }, { 194, -2776 }, { 195, -2257 }, { 196, -3360 }, { 197, -7396 },
            { 198, -4588 }, { 199, -1752 }, { 200, -2010 }, { 1, 126, 107, 2147483647, 20 },
            { 1, 89, 4, 623, 4 }, { 1, 113, 6, 2147483647, 8 }, { 1, 73, 701, 2147483647, 13 },
            { 1, 122, 49, 5469, 12 }, { 1, 192, 3, 1878, 20 }, { 1, 171, 132, 2147483647, 2 },
            { 1, 160, 43, 8240, 4 }, { 1, 177, 568, 2147483647, 5 }, { 1, 120, 73, 8854, 10 },
            { 1, 133, 364, 2147483647, 10 }, { 1, 96, 43, 7566, 7 }, { 1, 188, 96, 9886, 3 },
            { 1, 150, 284, 2147483647, 19 }, { 121, 174, 1, 1, 5 },
            { 121, 101, 962, 2147483647, 19 }, { 121, 191, 20, 4354, 16 },
            { 121, 142, 646, 2147483647, 9 }, { 121, 169, 60, 2147483647, 20 },
            { 121, 165, 10, 3249, 16 }, { 121, 160, 331, 2147483647, 10 },
            { 121, 106, 408, 2147483647, 14 }, { 121, 91, 1, 4032, 12 },
            { 126, 135, 833, 2147483647, 20 }, { 126, 181, 717, 2147483647, 16 },
            { 126, 110, 797, 2147483647, 2 }, { 126, 144, 104, 2147483647, 13 },
            { 135, 121, 1, 1, 7 }, { 135, 176, 589, 2147483647, 20 },
            { 135, 60, 80, 2147483647, 16 }, { 135, 132, 44, 5550, 19 }, { 135, 192, 27, 3266, 10 },
            { 135, 105, 344, 2147483647, 1 }, { 135, 158, 32, 4414, 1 }, { 135, 71, 56, 9298, 13 },
            { 135, 181, 610, 2147483647, 12 }, { 135, 152, 23, 3271, 17 },
            { 135, 157, 25, 4051, 20 }, { 2, 95, 70, 2147483647, 7 }, { 2, 104, 13, 2369, 2 },
            { 2, 192, 698, 2147483647, 11 }, { 2, 73, 20, 3848, 15 }, { 2, 114, 19, 4942, 19 },
            { 2, 59, 848, 2147483647, 14 }, { 2, 133, 1, 266, 1 }, { 2, 178, 304, 2147483647, 16 },
            { 2, 171, 692, 2147483647, 12 }, { 95, 140, 619, 2147483647, 16 },
            { 95, 184, 47, 9906, 9 }, { 95, 59, 10, 3373, 16 }, { 105, 185, 356, 2147483647, 19 },
            { 105, 170, 479, 2147483647, 14 }, { 105, 110, 547, 2147483647, 18 },
            { 105, 107, 15, 3775, 12 }, { 105, 60, 8, 1810, 12 }, { 105, 80, 558, 2147483647, 20 },
            { 105, 71, 91, 9311, 11 }, { 105, 98, 41, 6393, 3 }, { 105, 109, 906, 2147483647, 3 },
            { 105, 111, 252, 2147483647, 6 }, { 105, 198, 960, 2147483647, 15 },
            { 110, 183, 789, 2147483647, 16 }, { 110, 105, 1, 11, 19 }, { 110, 177, 21, 3137, 11 },
            { 140, 110, 1, 11, 20 }, { 140, 179, 340, 2147483647, 6 }, { 140, 196, 23, 2810, 14 },
            { 140, 123, 909, 2147483647, 11 }, { 140, 67, 19, 2458, 20 },
            { 140, 64, 38, 2147483647, 1 }, { 140, 148, 8, 2301, 1 }, { 140, 144, 58, 8002, 10 },
            { 140, 121, 146, 2147483647, 12 }, { 140, 56, 430, 2147483647, 4 },
            { 140, 52, 881, 2147483647, 10 }, { 140, 191, 1, 87, 1 }, { 140, 84, 41, 4306, 1 },
            { 140, 70, 74, 8268, 2 }, { 140, 163, 20, 4702, 3 }, { 140, 90, 333, 2147483647, 9 },
            { 3, 70, 921, 2147483647, 20 }, { 3, 102, 400, 2147483647, 14 }, { 3, 83, 55, 5714, 1 },
            { 3, 146, 19, 2253, 14 }, { 3, 176, 41, 2147483647, 18 }, { 3, 68, 16, 3327, 19 },
            { 3, 123, 400, 2147483647, 2 }, { 3, 171, 511, 2147483647, 13 },
            { 3, 181, 299, 2147483647, 7 }, { 3, 55, 21, 3199, 13 }, { 3, 141, 4, 1057, 16 },
            { 3, 164, 7, 651, 20 }, { 3, 98, 582, 2147483647, 14 }, { 3, 99, 91, 9175, 15 },
            { 3, 161, 971, 2147483647, 9 }, { 70, 104, 1, 28, 20 },
            { 70, 186, 603, 2147483647, 10 }, { 70, 112, 965, 2147483647, 8 },
            { 70, 91, 16, 5511, 16 }, { 70, 140, 10, 2147483647, 19 },
            { 70, 126, 382, 2147483647, 19 }, { 70, 184, 17, 4655, 15 }, { 70, 177, 63, 6216, 1 },
            { 70, 129, 5, 5454, 12 }, { 70, 196, 652, 2147483647, 10 },
            { 70, 144, 109, 2147483647, 11 }, { 70, 122, 4, 9646, 1 },
            { 70, 200, 972, 2147483647, 18 }, { 70, 194, 570, 2147483647, 2 },
            { 70, 108, 20, 2069, 2 }, { 104, 164, 493, 2147483647, 3 },
            { 104, 177, 860, 2147483647, 14 }, { 104, 90, 211, 2147483647, 7 },
            { 104, 99, 399, 2147483647, 17 }, { 104, 77, 37, 9638, 19 }, { 104, 130, 4, 967, 8 },
            { 104, 197, 7, 2147483647, 18 }, { 104, 166, 365, 2147483647, 3 },
            { 104, 111, 6, 7151, 17 }, { 104, 120, 123, 2147483647, 1 },
            { 104, 62, 34, 2147483647, 13 }, { 104, 158, 523, 2147483647, 14 },
            { 104, 79, 32, 3591, 15 }, { 104, 113, 896, 2147483647, 8 },
            { 104, 89, 418, 2147483647, 19 }, { 104, 92, 753, 2147483647, 15 },
            { 104, 87, 34, 4378, 14 }, { 4, 56, 616, 2147483647, 20 }, { 4, 123, 4, 9220, 11 },
            { 4, 155, 969, 2147483647, 5 }, { 4, 55, 966, 2147483647, 7 },
            { 4, 158, 177, 2147483647, 18 }, { 4, 85, 898, 2147483647, 4 }, { 4, 150, 1, 123, 4 },
            { 4, 178, 462, 2147483647, 9 }, { 4, 151, 305, 2147483647, 20 },
            { 4, 187, 905, 2147483647, 2 }, { 4, 193, 52, 2147483647, 2 }, { 4, 129, 24, 2787, 17 },
            { 4, 195, 824, 2147483647, 15 }, { 4, 191, 589, 2147483647, 2 },
            { 4, 83, 289, 2147483647, 18 }, { 56, 129, 1, 45, 20 }, { 56, 152, 24, 3036, 7 },
            { 56, 189, 327, 2147483647, 9 }, { 56, 140, 482, 2147483647, 3 },
            { 56, 195, 150, 2147483647, 3 }, { 68, 177, 1, 45, 20 }, { 68, 199, 1, 45, 3 },
            { 68, 153, 956, 2147483647, 1 }, { 68, 196, 21, 3695, 8 }, { 68, 70, 72, 9915, 10 },
            { 68, 64, 534, 2147483647, 14 }, { 68, 146, 33, 4958, 16 }, { 68, 115, 21, 4617, 13 },
            { 68, 84, 255, 2147483647, 1 }, { 68, 134, 632, 2147483647, 3 },
            { 68, 139, 478, 2147483647, 15 }, { 68, 61, 530, 2147483647, 13 },
            { 71, 164, 1, 45, 5 }, { 71, 68, 1, 45, 20 }, { 71, 114, 705, 2147483647, 19 },
            { 71, 180, 668, 2147483647, 4 }, { 71, 73, 34, 2147483647, 17 },
            { 71, 159, 968, 2147483647, 18 }, { 71, 145, 431, 2147483647, 16 },
            { 129, 71, 809, 2147483647, 20 }, { 129, 185, 152, 2147483647, 17 },
            { 129, 102, 26, 6025, 1 }, { 129, 60, 311, 2147483647, 1 }, { 129, 68, 5, 443, 20 },
            { 129, 183, 175, 2147483647, 12 }, { 129, 55, 836, 2147483647, 15 },
            { 129, 113, 28, 3584, 3 }, { 129, 166, 6, 3474, 12 }, { 129, 130, 579, 2147483647, 19 },
            { 129, 196, 744, 2147483647, 9 }, { 129, 62, 24, 3169, 5 }, { 129, 123, 6, 8114, 20 },
            { 129, 81, 29, 5719, 2 }, { 129, 170, 1, 93, 3 }, { 129, 153, 2, 417, 6 },
            { 5, 114, 20, 2147483647, 20 }, { 5, 126, 31, 3414, 15 },
            { 5, 98, 858, 2147483647, 17 }, { 5, 177, 56, 5993, 8 }, { 5, 63, 4, 8335, 11 },
            { 114, 139, 605, 2147483647, 20 }, { 114, 182, 587, 2147483647, 17 },
            { 114, 104, 9, 7610, 1 }, { 114, 78, 310, 2147483647, 16 }, { 114, 135, 26, 4029, 11 },
            { 114, 70, 60, 2147483647, 8 }, { 114, 161, 13, 3850, 1 },
            { 139, 179, 870, 2147483647, 20 }, { 139, 98, 607, 2147483647, 19 },
            { 139, 65, 488, 2147483647, 19 }, { 6, 73, 131, 2147483647, 20 },
            { 6, 172, 546, 2147483647, 17 }, { 6, 197, 846, 2147483647, 20 },
            { 6, 164, 32, 7052, 6 }, { 6, 166, 152, 2147483647, 20 }, { 6, 156, 9, 2780, 3 },
            { 6, 174, 485, 2147483647, 6 }, { 6, 56, 24, 2994, 9 }, { 6, 150, 436, 2147483647, 14 },
            { 6, 55, 49, 2147483647, 17 }, { 6, 157, 574, 2147483647, 16 },
            { 6, 186, 261, 2147483647, 11 }, { 6, 93, 42, 4154, 18 }, { 6, 76, 64, 2147483647, 4 },
            { 73, 92, 947, 2147483647, 20 }, { 73, 181, 1, 32, 19 }, { 73, 127, 49, 7060, 12 },
            { 73, 160, 24, 2422, 12 }, { 73, 82, 534, 2147483647, 2 },
            { 73, 98, 861, 2147483647, 17 }, { 73, 89, 196, 2147483647, 3 },
            { 73, 150, 23, 2415, 10 }, { 73, 188, 30, 4484, 6 }, { 73, 123, 126, 2147483647, 19 },
            { 73, 53, 223, 2147483647, 8 }, { 73, 125, 534, 2147483647, 10 },
            { 73, 153, 4, 1504, 4 }, { 73, 130, 721, 2147483647, 3 }, { 73, 104, 3, 3185, 10 },
            { 73, 63, 320, 2147483647, 10 }, { 73, 185, 459, 2147483647, 11 },
            { 92, 97, 1, 32, 20 }, { 92, 190, 974, 2147483647, 3 },
            { 92, 121, 369, 2147483647, 18 }, { 92, 55, 83, 9894, 7 }, { 92, 118, 68, 7213, 5 },
            { 92, 84, 644, 2147483647, 8 }, { 92, 65, 9, 5822, 11 },
            { 92, 139, 932, 2147483647, 19 }, { 92, 104, 21, 4487, 20 },
            { 92, 58, 9, 2147483647, 12 }, { 92, 149, 44, 2147483647, 11 },
            { 92, 134, 15, 1427, 1 }, { 92, 169, 11, 1951, 11 }, { 92, 142, 240, 2147483647, 5 },
            { 97, 122, 1, 32, 14 }, { 97, 175, 12, 2198, 14 }, { 97, 192, 775, 2147483647, 4 },
            { 97, 176, 56, 2147483647, 10 }, { 97, 74, 39, 3886, 19 }, { 122, 184, 1, 32, 17 },
            { 122, 187, 968, 2147483647, 20 }, { 122, 174, 1, 32, 18 }, { 122, 193, 17, 2094, 14 },
            { 122, 55, 22, 2333, 7 }, { 122, 179, 82, 9508, 3 }, { 122, 77, 641, 2147483647, 2 },
            { 122, 125, 17, 8602, 5 }, { 122, 199, 12, 6645, 2 }, { 122, 106, 12, 2028, 10 },
            { 122, 89, 4, 493, 6 }, { 122, 85, 12, 9556, 18 }, { 7, 150, 14, 2147483647, 20 },
            { 7, 131, 48, 2147483647, 13 }, { 7, 161, 2, 4923, 16 }, { 7, 136, 829, 2147483647, 9 },
            { 7, 185, 422, 2147483647, 1 }, { 7, 64, 16, 6699, 2 }, { 7, 183, 44, 7760, 12 },
            { 7, 160, 570, 2147483647, 13 }, { 7, 86, 112, 2147483647, 18 },
            { 7, 140, 44, 2147483647, 7 }, { 7, 159, 935, 2147483647, 8 }, { 53, 134, 1, 45, 9 },
            { 53, 175, 1, 45, 6 }, { 53, 76, 27, 8048, 9 }, { 134, 180, 1, 45, 20 },
            { 134, 197, 667, 2147483647, 13 }, { 134, 190, 36, 4296, 5 },
            { 134, 194, 10, 1779, 12 }, { 134, 107, 633, 2147483647, 12 },
            { 150, 53, 472, 2147483647, 20 }, { 150, 151, 1, 45, 1 },
            { 150, 174, 965, 2147483647, 8 }, { 150, 167, 26, 4263, 7 }, { 150, 59, 21, 2766, 10 },
            { 150, 139, 919, 2147483647, 4 }, { 150, 69, 18, 2602, 13 },
            { 150, 56, 73, 2147483647, 15 }, { 150, 118, 5, 7982, 1 },
            { 150, 185, 744, 2147483647, 12 }, { 150, 191, 31, 8397, 3 },
            { 150, 79, 903, 2147483647, 20 }, { 150, 134, 2, 3564, 15 },
            { 150, 197, 528, 2147483647, 4 }, { 150, 125, 579, 2147483647, 12 },
            { 150, 178, 41, 5497, 13 }, { 8, 127, 1, 29, 20 }, { 8, 71, 11, 4672, 19 },
            { 8, 67, 5, 1413, 18 }, { 8, 193, 214, 2147483647, 19 }, { 8, 123, 393, 2147483647, 9 },
            { 8, 60, 796, 2147483647, 8 }, { 8, 99, 413, 2147483647, 17 }, { 8, 151, 16, 1616, 7 },
            { 8, 166, 60, 2147483647, 12 }, { 8, 59, 350, 2147483647, 1 },
            { 8, 159, 75, 2147483647, 2 }, { 8, 140, 14, 9486, 20 }, { 8, 61, 18, 4251, 10 },
            { 52, 143, 33, 2147483647, 20 }, { 52, 146, 763, 2147483647, 7 },
            { 52, 59, 182, 2147483647, 17 }, { 52, 198, 519, 2147483647, 12 },
            { 52, 88, 27, 2725, 6 }, { 52, 183, 199, 2147483647, 4 },
            { 52, 197, 937, 2147483647, 3 }, { 52, 96, 7, 1080, 13 },
            { 52, 161, 233, 2147483647, 3 }, { 52, 157, 606, 2147483647, 14 },
            { 52, 144, 23, 6011, 6 }, { 52, 179, 17, 4134, 3 }, { 52, 134, 8, 2878, 14 },
            { 52, 184, 45, 2147483647, 9 }, { 52, 139, 809, 2147483647, 6 }, { 52, 61, 4, 409, 12 },
            { 52, 132, 451, 2147483647, 18 }, { 76, 52, 563, 2147483647, 20 },
            { 76, 181, 596, 2147483647, 20 }, { 76, 187, 73, 2147483647, 14 },
            { 76, 121, 2, 457, 17 }, { 127, 148, 689, 2147483647, 20 }, { 127, 182, 1, 29, 18 },
            { 127, 123, 200, 2147483647, 9 }, { 127, 76, 405, 2147483647, 8 },
            { 127, 74, 355, 2147483647, 7 }, { 143, 161, 193, 2147483647, 18 },
            { 143, 159, 665, 2147483647, 17 }, { 143, 117, 33, 6845, 7 }, { 143, 194, 34, 6106, 5 },
            { 143, 75, 152, 2147483647, 6 }, { 143, 138, 108, 2147483647, 8 },
            { 143, 178, 340, 2147483647, 17 }, { 143, 140, 44, 7188, 11 },
            { 143, 191, 913, 2147483647, 19 }, { 143, 164, 24, 2147483647, 9 },
            { 143, 84, 70, 8979, 4 }, { 143, 97, 69, 7649, 16 }, { 148, 76, 1, 29, 20 },
            { 148, 170, 1, 29, 20 }, { 148, 93, 195, 2147483647, 16 },
            { 148, 58, 139, 2147483647, 14 }, { 148, 63, 6, 713, 10 }, { 148, 155, 84, 8846, 5 },
            { 148, 87, 21, 2147483647, 20 }, { 148, 75, 629, 2147483647, 16 },
            { 148, 95, 12, 1734, 1 }, { 148, 124, 80, 7970, 18 }, { 148, 143, 483, 2147483647, 7 },
            { 9, 142, 40, 2147483647, 20 }, { 9, 145, 15, 3013, 10 }, { 9, 176, 8, 1690, 19 },
            { 9, 63, 325, 2147483647, 4 }, { 9, 89, 295, 2147483647, 20 },
            { 9, 110, 345, 2147483647, 11 }, { 9, 128, 19, 6145, 2 }, { 9, 182, 77, 9997, 4 },
            { 9, 175, 50, 5835, 9 }, { 9, 126, 998, 2147483647, 16 },
            { 9, 156, 587, 2147483647, 17 }, { 9, 115, 4, 3233, 4 }, { 9, 82, 7, 2147483647, 20 },
            { 9, 84, 457, 2147483647, 15 }, { 9, 109, 67, 7956, 18 }, { 9, 60, 56, 5784, 4 },
            { 61, 179, 648, 2147483647, 18 }, { 61, 55, 21, 3057, 6 },
            { 61, 199, 110, 2147483647, 13 }, { 61, 127, 6, 4717, 13 }, { 61, 160, 7, 2283, 16 },
            { 142, 61, 772, 2147483647, 15 }, { 142, 158, 1, 22, 2 }, { 142, 188, 3, 4691, 20 },
            { 142, 64, 1, 6914, 2 }, { 142, 196, 125, 2147483647, 18 },
            { 142, 123, 15, 2147483647, 20 }, { 142, 70, 726, 2147483647, 11 },
            { 142, 96, 162, 2147483647, 11 }, { 142, 134, 127, 2147483647, 17 },
            { 142, 165, 371, 2147483647, 11 }, { 142, 162, 528, 2147483647, 14 },
            { 142, 185, 3, 438, 12 }, { 142, 179, 25, 6905, 13 }, { 142, 161, 524, 2147483647, 18 },
            { 142, 163, 598, 2147483647, 6 }, { 142, 55, 39, 9411, 20 }, { 10, 54, 1, 18, 13 },
            { 10, 147, 572, 2147483647, 17 }, { 10, 170, 895, 2147483647, 17 },
            { 10, 135, 77, 2147483647, 7 }, { 10, 156, 6, 736, 16 },
            { 10, 159, 555, 2147483647, 18 }, { 10, 197, 297, 2147483647, 9 },
            { 54, 147, 1, 18, 20 }, { 54, 158, 452, 2147483647, 20 },
            { 54, 171, 383, 2147483647, 9 }, { 54, 126, 989, 2147483647, 3 },
            { 54, 197, 20, 6703, 20 }, { 54, 117, 2, 206, 4 }, { 54, 104, 432, 2147483647, 3 },
            { 54, 51, 666, 2147483647, 3 }, { 54, 156, 650, 2147483647, 13 },
            { 147, 161, 1, 18, 20 }, { 147, 197, 48, 2147483647, 20 }, { 147, 109, 2, 723, 18 },
            { 147, 58, 47, 7454, 5 }, { 147, 52, 820, 2147483647, 16 }, { 147, 141, 83, 9109, 10 },
            { 147, 164, 17, 2963, 14 }, { 147, 156, 57, 7713, 3 }, { 147, 193, 21, 2047, 1 },
            { 147, 136, 627, 2147483647, 14 }, { 147, 157, 629, 2147483647, 16 },
            { 147, 179, 50, 6956, 13 }, { 147, 189, 859, 2147483647, 6 },
            { 147, 155, 15, 4362, 11 }, { 147, 120, 69, 9967, 7 },
            { 147, 129, 651, 2147483647, 10 }, { 147, 51, 55, 5702, 6 },
            { 11, 106, 880, 2147483647, 20 }, { 11, 92, 887, 2147483647, 20 },
            { 11, 80, 58, 8221, 18 }, { 11, 194, 66, 6916, 6 }, { 11, 136, 34, 7654, 2 },
            { 11, 142, 522, 2147483647, 5 }, { 11, 63, 57, 7709, 7 },
            { 11, 113, 469, 2147483647, 19 }, { 11, 75, 16, 1860, 8 },
            { 11, 115, 717, 2147483647, 3 }, { 11, 127, 39, 8917, 15 }, { 11, 61, 1, 56, 16 },
            { 69, 196, 149, 2147483647, 20 }, { 69, 142, 868, 2147483647, 14 },
            { 69, 140, 4, 2147483647, 5 }, { 69, 175, 936, 2147483647, 4 }, { 69, 74, 16, 1877, 4 },
            { 69, 130, 753, 2147483647, 9 }, { 69, 157, 57, 2147483647, 11 },
            { 69, 164, 12, 7900, 6 }, { 106, 115, 848, 2147483647, 20 }, { 106, 114, 15, 5272, 11 },
            { 106, 194, 63, 8813, 6 }, { 106, 129, 69, 8620, 14 },
            { 106, 162, 251, 2147483647, 11 }, { 106, 176, 322, 2147483647, 12 },
            { 106, 65, 842, 2147483647, 4 }, { 106, 198, 12, 8777, 6 }, { 106, 78, 2, 985, 15 },
            { 106, 64, 107, 2147483647, 18 }, { 106, 199, 9, 2147483647, 8 },
            { 106, 93, 762, 2147483647, 9 }, { 106, 195, 84, 2147483647, 6 },
            { 115, 69, 1, 16, 20 }, { 115, 156, 1, 16, 14 }, { 115, 152, 662, 2147483647, 5 },
            { 115, 75, 803, 2147483647, 20 }, { 12, 107, 766, 2147483647, 11 },
            { 12, 78, 339, 2147483647, 13 }, { 12, 66, 25, 3939, 19 },
            { 12, 98, 439, 2147483647, 16 }, { 12, 136, 456, 2147483647, 14 },
            { 12, 56, 16, 2735, 10 }, { 12, 55, 70, 7604, 20 }, { 12, 125, 48, 8941, 4 },
            { 107, 200, 392, 2147483647, 20 }, { 107, 185, 969, 2147483647, 9 },
            { 107, 176, 7, 5726, 8 }, { 107, 187, 37, 4489, 19 }, { 107, 99, 23, 4674, 15 },
            { 107, 65, 786, 2147483647, 4 }, { 107, 183, 312, 2147483647, 4 },
            { 107, 93, 13, 7708, 2 }, { 107, 113, 805, 2147483647, 17 },
            { 107, 82, 183, 2147483647, 8 }, { 107, 190, 357, 2147483647, 17 },
            { 107, 85, 8, 836, 2 }, { 107, 179, 563, 2147483647, 1 }, { 107, 184, 16, 8367, 2 },
            { 107, 142, 992, 2147483647, 10 }, { 107, 143, 76, 2147483647, 3 },
            { 107, 100, 698, 2147483647, 10 }, { 107, 172, 387, 2147483647, 7 },
            { 13, 81, 363, 2147483647, 14 }, { 13, 57, 1, 2920, 5 },
            { 13, 113, 950, 2147483647, 7 }, { 13, 152, 321, 2147483647, 13 },
            { 13, 93, 656, 2147483647, 11 }, { 13, 99, 82, 2147483647, 2 },
            { 13, 53, 13, 1214, 19 }, { 13, 179, 76, 9141, 16 }, { 13, 198, 564, 2147483647, 1 },
            { 13, 130, 81, 8935, 19 }, { 13, 158, 49, 7805, 2 }, { 13, 184, 58, 6452, 16 },
            { 13, 133, 104, 2147483647, 11 }, { 13, 76, 25, 3216, 7 },
            { 13, 193, 935, 2147483647, 18 }, { 77, 182, 642, 2147483647, 20 },
            { 77, 188, 1, 10, 19 }, { 77, 154, 1, 10, 8 }, { 77, 86, 632, 2147483647, 14 },
            { 77, 172, 642, 2147483647, 3 }, { 77, 144, 103, 2147483647, 19 },
            { 77, 132, 25, 9038, 4 }, { 77, 99, 370, 2147483647, 9 },
            { 77, 63, 142, 2147483647, 8 }, { 77, 79, 598, 2147483647, 13 },
            { 77, 164, 55, 9888, 7 }, { 81, 89, 835, 2147483647, 8 },
            { 81, 194, 598, 2147483647, 20 }, { 81, 129, 9, 1386, 18 }, { 81, 83, 32, 9254, 10 },
            { 89, 133, 367, 2147483647, 5 }, { 89, 125, 24, 2147483647, 8 },
            { 89, 122, 27, 3786, 2 }, { 89, 119, 9, 1360, 6 }, { 89, 156, 247, 2147483647, 15 },
            { 89, 162, 519, 2147483647, 4 }, { 89, 127, 8, 2450, 4 },
            { 89, 153, 868, 2147483647, 7 }, { 133, 77, 1, 10, 20 }, { 133, 150, 5, 9673, 6 },
            { 133, 123, 37, 4167, 18 }, { 133, 161, 717, 2147483647, 8 },
            { 133, 132, 186, 2147483647, 8 }, { 133, 92, 708, 2147483647, 20 },
            { 133, 90, 12, 2875, 1 }, { 14, 51, 336, 2147483647, 13 }, { 14, 63, 7, 687, 8 },
            { 14, 185, 38, 7679, 3 }, { 14, 54, 69, 9563, 13 }, { 14, 189, 19, 4370, 10 },
            { 14, 139, 18, 7376, 7 }, { 14, 105, 562, 2147483647, 15 }, { 14, 123, 12, 6895, 19 },
            { 14, 103, 44, 7112, 13 }, { 14, 62, 44, 5822, 6 }, { 14, 114, 285, 2147483647, 17 },
            { 14, 61, 43, 2147483647, 4 }, { 51, 192, 104, 2147483647, 20 },
            { 51, 160, 27, 2147483647, 7 }, { 51, 198, 421, 2147483647, 18 },
            { 51, 71, 156, 2147483647, 11 }, { 51, 81, 8, 3892, 1 }, { 51, 66, 16, 4923, 7 },
            { 51, 171, 52, 7001, 10 }, { 51, 95, 42, 7526, 15 }, { 51, 188, 517, 2147483647, 19 },
            { 51, 142, 49, 7044, 1 }, { 51, 135, 22, 2147483647, 14 },
            { 51, 175, 858, 2147483647, 2 }, { 51, 152, 367, 2147483647, 18 },
            { 51, 143, 774, 2147483647, 9 }, { 51, 62, 734, 2147483647, 18 },
            { 51, 128, 3, 7982, 1 }, { 51, 163, 836, 2147483647, 13 },
            { 51, 200, 325, 2147483647, 8 }, { 15, 108, 1, 4, 20 },
            { 15, 170, 358, 2147483647, 13 }, { 15, 176, 129, 2147483647, 10 },
            { 15, 187, 64, 7865, 8 }, { 15, 59, 4, 715, 9 }, { 15, 169, 558, 2147483647, 18 },
            { 108, 183, 985, 2147483647, 20 }, { 108, 198, 1, 4, 6 },
            { 108, 181, 432, 2147483647, 5 }, { 108, 192, 644, 2147483647, 3 },
            { 108, 86, 4, 4052, 19 }, { 108, 72, 594, 2147483647, 16 }, { 108, 111, 83, 8665, 9 },
            { 108, 160, 62, 6810, 16 }, { 108, 83, 863, 2147483647, 5 },
            { 16, 65, 917, 2147483647, 20 }, { 16, 70, 5, 6264, 16 }, { 16, 91, 25, 2559, 18 },
            { 16, 169, 335, 2147483647, 13 }, { 16, 60, 1, 4474, 17 },
            { 16, 72, 116, 2147483647, 5 }, { 16, 192, 73, 8487, 19 },
            { 16, 121, 185, 2147483647, 6 }, { 16, 51, 72, 2147483647, 8 },
            { 65, 191, 632, 2147483647, 20 }, { 65, 197, 1, 17, 2 },
            { 65, 180, 464, 2147483647, 4 }, { 65, 123, 35, 4017, 6 }, { 65, 67, 3, 4848, 16 },
            { 17, 94, 718, 2147483647, 18 }, { 17, 106, 6, 4391, 1 },
            { 17, 122, 555, 2147483647, 20 }, { 17, 195, 67, 7506, 15 },
            { 17, 191, 890, 2147483647, 1 }, { 17, 87, 2, 209, 12 }, { 17, 68, 11, 5814, 2 },
            { 17, 156, 857, 2147483647, 7 }, { 94, 179, 1, 20, 20 },
            { 94, 187, 228, 2147483647, 11 }, { 94, 197, 372, 2147483647, 2 },
            { 94, 188, 93, 2147483647, 15 }, { 94, 153, 327, 2147483647, 6 },
            { 94, 155, 454, 2147483647, 2 }, { 94, 76, 20, 6658, 6 },
            { 94, 53, 262, 2147483647, 18 }, { 94, 55, 677, 2147483647, 2 },
            { 94, 105, 382, 2147483647, 1 }, { 94, 91, 186, 2147483647, 18 }, { 18, 86, 1, 29, 15 },
            { 18, 122, 56, 5828, 15 }, { 18, 83, 188, 2147483647, 3 },
            { 86, 160, 997, 2147483647, 20 }, { 86, 200, 172, 2147483647, 20 },
            { 86, 106, 2, 4665, 17 }, { 86, 188, 3, 5339, 1 }, { 86, 153, 520, 2147483647, 14 },
            { 86, 169, 584, 2147483647, 11 }, { 86, 115, 549, 2147483647, 2 },
            { 86, 98, 783, 2147483647, 6 }, { 86, 174, 75, 9764, 3 }, { 86, 112, 53, 5703, 18 },
            { 86, 100, 10, 7830, 2 }, { 86, 116, 161, 2147483647, 14 }, { 86, 172, 38, 4758, 11 },
            { 86, 72, 22, 6458, 8 }, { 19, 85, 747, 2147483647, 20 }, { 19, 116, 4, 3562, 13 },
            { 19, 197, 781, 2147483647, 15 }, { 19, 94, 314, 2147483647, 6 },
            { 19, 124, 26, 6311, 1 }, { 19, 171, 17, 2972, 6 }, { 19, 177, 16, 5605, 5 },
            { 19, 97, 317, 2147483647, 10 }, { 19, 111, 65, 7488, 7 },
            { 19, 164, 903, 2147483647, 14 }, { 19, 119, 207, 2147483647, 19 },
            { 19, 140, 659, 2147483647, 12 }, { 19, 148, 761, 2147483647, 17 },
            { 19, 55, 41, 6213, 7 }, { 19, 131, 556, 2147483647, 7 }, { 85, 171, 1, 25, 13 },
            { 85, 156, 1, 25, 9 }, { 85, 104, 16, 7673, 17 }, { 85, 70, 36, 7801, 10 },
            { 85, 155, 800, 2147483647, 5 }, { 85, 153, 19, 4949, 13 }, { 85, 119, 18, 3870, 16 },
            { 85, 200, 12, 2147483647, 6 }, { 85, 142, 561, 2147483647, 1 },
            { 85, 114, 676, 2147483647, 17 }, { 85, 139, 805, 2147483647, 2 },
            { 85, 72, 182, 2147483647, 2 }, { 85, 53, 122, 2147483647, 17 },
            { 85, 51, 559, 2147483647, 13 }, { 85, 175, 11, 7428, 9 }, { 85, 131, 7, 1757, 20 },
            { 20, 57, 1, 1, 9 }, { 20, 58, 604, 2147483647, 18 }, { 20, 194, 50, 5128, 13 },
            { 20, 55, 950, 2147483647, 7 }, { 20, 96, 20, 2147483647, 2 },
            { 20, 111, 25, 2651, 17 }, { 20, 64, 12, 3459, 1 }, { 20, 167, 21, 3527, 12 },
            { 20, 76, 21, 3425, 17 }, { 20, 92, 6, 710, 4 }, { 20, 69, 8, 8772, 1 },
            { 20, 122, 482, 2147483647, 9 }, { 20, 192, 486, 2147483647, 13 },
            { 20, 156, 53, 9987, 15 }, { 20, 63, 19, 6658, 10 }, { 57, 155, 691, 2147483647, 20 },
            { 57, 156, 1, 1, 20 }, { 57, 198, 96, 2147483647, 7 }, { 57, 130, 10, 5415, 3 },
            { 57, 133, 373, 2147483647, 3 }, { 57, 107, 19, 3182, 5 },
            { 57, 154, 515, 2147483647, 9 }, { 57, 151, 8, 1312, 10 },
            { 57, 82, 191, 2147483647, 6 }, { 57, 147, 509, 2147483647, 14 },
            { 57, 186, 931, 2147483647, 17 }, { 57, 66, 21, 3703, 9 },
            { 57, 140, 290, 2147483647, 11 }, { 21, 87, 1, 16, 2 }, { 21, 145, 19, 2041, 10 },
            { 21, 183, 654, 2147483647, 10 }, { 21, 106, 857, 2147483647, 14 },
            { 21, 54, 902, 2147483647, 2 }, { 21, 197, 3, 7597, 6 }, { 21, 113, 10, 1033, 17 },
            { 21, 177, 818, 2147483647, 17 }, { 21, 156, 606, 2147483647, 16 },
            { 72, 154, 1, 16, 13 }, { 72, 187, 1, 16, 20 }, { 72, 120, 801, 2147483647, 12 },
            { 72, 96, 474, 2147483647, 9 }, { 72, 73, 24, 2923, 8 }, { 72, 101, 23, 2758, 4 },
            { 72, 153, 384, 2147483647, 14 }, { 72, 99, 636, 2147483647, 18 },
            { 72, 66, 39, 8346, 16 }, { 72, 168, 9, 1076, 13 }, { 72, 95, 40, 6499, 2 },
            { 72, 111, 62, 7388, 5 }, { 87, 72, 1, 16, 6 }, { 87, 86, 26, 5286, 19 },
            { 87, 55, 17, 3009, 2 }, { 87, 156, 17, 1985, 13 }, { 22, 117, 1, 20, 9 },
            { 22, 146, 104, 2147483647, 11 }, { 22, 169, 7, 1730, 8 }, { 22, 92, 10, 1950, 2 },
            { 22, 143, 977, 2147483647, 9 }, { 22, 121, 199, 2147483647, 5 },
            { 22, 51, 6, 2309, 4 }, { 22, 103, 614, 2147483647, 1 },
            { 22, 119, 437, 2147483647, 2 }, { 22, 91, 59, 6037, 3 },
            { 22, 197, 961, 2147483647, 6 }, { 22, 81, 22, 3105, 13 },
            { 22, 97, 474, 2147483647, 5 }, { 22, 90, 719, 2147483647, 1 }, { 60, 176, 1, 20, 10 },
            { 60, 132, 33, 5575, 18 }, { 60, 79, 560, 2147483647, 16 },
            { 60, 199, 366, 2147483647, 7 }, { 60, 55, 945, 2147483647, 7 },
            { 60, 77, 24, 7999, 18 }, { 60, 122, 867, 2147483647, 12 }, { 60, 196, 26, 3133, 20 },
            { 117, 119, 1, 20, 20 }, { 117, 153, 84, 2147483647, 4 }, { 117, 135, 13, 1816, 7 },
            { 119, 60, 1, 20, 19 }, { 119, 154, 711, 2147483647, 20 }, { 119, 146, 7, 709, 18 },
            { 119, 172, 6, 8551, 8 }, { 119, 163, 271, 2147483647, 10 },
            { 119, 180, 935, 2147483647, 1 }, { 119, 126, 329, 2147483647, 6 },
            { 119, 52, 14, 2503, 1 }, { 119, 102, 30, 2147483647, 17 }, { 119, 67, 34, 9928, 16 },
            { 119, 111, 191, 2147483647, 5 }, { 119, 179, 855, 2147483647, 4 },
            { 119, 62, 2, 204, 5 }, { 119, 148, 719, 2147483647, 17 },
            { 119, 88, 978, 2147483647, 16 }, { 119, 84, 10, 1028, 11 }, { 119, 87, 16, 1679, 14 },
            { 23, 101, 781, 2147483647, 20 }, { 23, 153, 290, 2147483647, 2 },
            { 23, 171, 705, 2147483647, 20 }, { 23, 52, 3, 4064, 14 }, { 23, 131, 10, 2216, 2 },
            { 23, 78, 852, 2147483647, 3 }, { 23, 118, 749, 2147483647, 8 },
            { 23, 64, 37, 4544, 11 }, { 23, 179, 4, 1885, 15 }, { 23, 119, 980, 2147483647, 13 },
            { 23, 148, 47, 5911, 11 }, { 23, 99, 11, 9285, 19 }, { 63, 187, 190, 2147483647, 12 },
            { 63, 165, 256, 2147483647, 17 }, { 63, 90, 8, 8477, 19 },
            { 63, 173, 55, 2147483647, 4 }, { 101, 63, 891, 2147483647, 14 },
            { 101, 193, 572, 2147483647, 20 }, { 101, 77, 67, 2147483647, 11 },
            { 101, 81, 74, 7782, 20 }, { 101, 199, 450, 2147483647, 6 }, { 101, 171, 10, 8658, 8 },
            { 101, 185, 83, 9397, 20 }, { 101, 131, 97, 2147483647, 13 }, { 101, 76, 12, 1186, 12 },
            { 101, 149, 69, 8115, 10 }, { 101, 139, 750, 2147483647, 1 }, { 24, 82, 1, 6, 20 },
            { 24, 65, 551, 2147483647, 3 }, { 24, 153, 622, 2147483647, 18 },
            { 24, 53, 790, 2147483647, 16 }, { 24, 155, 64, 8629, 20 },
            { 24, 198, 629, 2147483647, 11 }, { 24, 92, 176, 2147483647, 18 },
            { 24, 148, 9, 8907, 5 }, { 24, 133, 600, 2147483647, 12 }, { 24, 56, 79, 9965, 19 },
            { 24, 163, 993, 2147483647, 15 }, { 24, 99, 21, 3655, 6 }, { 82, 154, 1, 6, 6 },
            { 82, 155, 1, 6, 1 }, { 82, 100, 152, 2147483647, 16 }, { 82, 112, 66, 7308, 20 },
            { 82, 144, 506, 2147483647, 5 }, { 82, 106, 921, 2147483647, 6 },
            { 82, 117, 12, 6736, 14 }, { 82, 190, 8, 3922, 5 }, { 82, 160, 5, 732, 14 },
            { 82, 70, 34, 9037, 17 }, { 82, 90, 647, 2147483647, 14 },
            { 25, 84, 62, 2147483647, 1 }, { 25, 180, 169, 2147483647, 17 }, { 84, 128, 1, 27, 20 },
            { 84, 180, 1, 27, 20 }, { 84, 121, 622, 2147483647, 18 },
            { 84, 165, 236, 2147483647, 4 }, { 84, 135, 602, 2147483647, 8 },
            { 84, 125, 769, 2147483647, 14 }, { 84, 171, 29, 6883, 20 },
            { 84, 150, 621, 2147483647, 20 }, { 84, 149, 985, 2147483647, 14 },
            { 84, 70, 55, 6447, 17 }, { 84, 56, 922, 2147483647, 1 },
            { 84, 126, 211, 2147483647, 19 }, { 84, 66, 663, 2147483647, 9 },
            { 84, 105, 81, 2147483647, 20 }, { 84, 151, 42, 4525, 7 },
            { 84, 61, 641, 2147483647, 15 }, { 128, 157, 1, 27, 18 },
            { 128, 158, 334, 2147483647, 2 }, { 128, 181, 679, 2147483647, 11 },
            { 128, 188, 859, 2147483647, 8 }, { 128, 108, 42, 4376, 9 }, { 128, 152, 8, 2752, 18 },
            { 128, 176, 5, 3009, 16 }, { 128, 89, 56, 5842, 1 }, { 128, 114, 505, 2147483647, 18 },
            { 128, 199, 3, 680, 2 }, { 128, 155, 26, 7080, 11 }, { 128, 127, 17, 3249, 6 },
            { 26, 93, 780, 2147483647, 2 }, { 26, 169, 372, 2147483647, 5 },
            { 26, 179, 85, 2147483647, 17 }, { 26, 145, 896, 2147483647, 8 },
            { 26, 55, 869, 2147483647, 13 }, { 26, 103, 32, 8555, 9 }, { 26, 63, 17, 5690, 17 },
            { 26, 68, 1, 3027, 17 }, { 26, 151, 1, 3565, 6 }, { 58, 157, 1, 7, 14 },
            { 58, 165, 239, 2147483647, 9 }, { 58, 169, 85, 8479, 20 },
            { 58, 121, 36, 2147483647, 10 }, { 58, 118, 221, 2147483647, 20 },
            { 58, 74, 171, 2147483647, 8 }, { 58, 166, 26, 3207, 7 },
            { 58, 114, 736, 2147483647, 17 }, { 58, 196, 197, 2147483647, 14 },
            { 58, 167, 973, 2147483647, 2 }, { 58, 189, 143, 2147483647, 2 },
            { 58, 68, 768, 2147483647, 17 }, { 58, 186, 9, 1917, 5 },
            { 58, 142, 739, 2147483647, 17 }, { 62, 162, 1, 7, 20 }, { 62, 58, 454, 2147483647, 8 },
            { 62, 194, 118, 2147483647, 16 }, { 62, 189, 1, 2902, 13 }, { 62, 69, 19, 2850, 18 },
            { 62, 145, 56, 2147483647, 15 }, { 62, 147, 724, 2147483647, 19 },
            { 62, 134, 19, 2147483647, 9 }, { 62, 138, 69, 2147483647, 15 },
            { 62, 79, 32, 6519, 8 }, { 62, 59, 12, 9780, 20 }, { 62, 176, 930, 2147483647, 19 },
            { 62, 125, 55, 8245, 8 }, { 93, 62, 1, 7, 17 }, { 93, 142, 1, 8087, 12 },
            { 93, 123, 238, 2147483647, 4 }, { 93, 128, 743, 2147483647, 11 },
            { 27, 98, 638, 2147483647, 20 }, { 27, 76, 69, 7914, 18 },
            { 27, 69, 105, 2147483647, 11 }, { 27, 131, 642, 2147483647, 6 },
            { 79, 167, 270, 2147483647, 20 }, { 79, 199, 1, 9, 11 }, { 79, 100, 60, 7456, 12 },
            { 79, 93, 45, 5238, 20 }, { 79, 97, 8, 8866, 9 }, { 79, 133, 135, 2147483647, 10 },
            { 79, 123, 3, 830, 17 }, { 79, 146, 24, 5010, 13 }, { 79, 112, 448, 2147483647, 17 },
            { 79, 152, 46, 6506, 3 }, { 79, 168, 30, 3972, 8 }, { 79, 56, 602, 2147483647, 4 },
            { 98, 79, 1, 9, 2 }, { 98, 177, 9, 9973, 16 }, { 98, 200, 43, 5602, 16 },
            { 98, 151, 39, 4679, 18 }, { 98, 187, 32, 3485, 6 }, { 98, 130, 49, 9028, 3 },
            { 28, 136, 1, 30, 13 }, { 28, 113, 705, 2147483647, 6 }, { 28, 189, 28, 7992, 16 },
            { 28, 79, 340, 2147483647, 1 }, { 66, 185, 1, 30, 5 }, { 66, 63, 674, 2147483647, 1 },
            { 66, 110, 1, 261, 10 }, { 136, 66, 303, 2147483647, 20 }, { 136, 198, 1, 30, 18 },
            { 136, 162, 4, 1343, 13 }, { 136, 192, 7, 1283, 17 }, { 136, 166, 2, 1135, 14 },
            { 136, 185, 73, 7249, 2 }, { 29, 123, 1, 17, 14 }, { 29, 104, 12, 1154, 1 },
            { 29, 61, 758, 2147483647, 16 }, { 29, 58, 71, 2147483647, 9 },
            { 29, 119, 26, 3590, 4 }, { 29, 111, 990, 2147483647, 10 },
            { 29, 134, 685, 2147483647, 18 }, { 29, 93, 14, 1381, 11 },
            { 29, 106, 999, 2147483647, 15 }, { 29, 91, 570, 2147483647, 1 },
            { 29, 98, 87, 9113, 13 }, { 29, 188, 32, 8365, 5 }, { 29, 77, 129, 2147483647, 13 },
            { 29, 192, 473, 2147483647, 14 }, { 123, 130, 387, 2147483647, 20 },
            { 123, 191, 775, 2147483647, 18 }, { 123, 70, 757, 2147483647, 6 },
            { 130, 167, 41, 2147483647, 20 }, { 130, 178, 232, 2147483647, 18 },
            { 130, 106, 779, 2147483647, 5 }, { 130, 145, 358, 2147483647, 1 },
            { 130, 53, 7, 3906, 5 }, { 130, 96, 776, 2147483647, 20 }, { 130, 108, 58, 6416, 4 },
            { 130, 111, 818, 2147483647, 14 }, { 130, 52, 3, 266, 14 }, { 130, 199, 46, 7409, 9 },
            { 130, 160, 816, 2147483647, 3 }, { 130, 69, 492, 2147483647, 18 },
            { 130, 183, 765, 2147483647, 3 }, { 130, 196, 18, 4578, 1 },
            { 130, 139, 50, 2147483647, 14 }, { 130, 77, 34, 7871, 5 }, { 130, 142, 38, 4024, 12 },
            { 130, 97, 521, 2147483647, 4 }, { 30, 138, 616, 2147483647, 15 },
            { 30, 87, 59, 9068, 2 }, { 30, 142, 676, 2147483647, 10 }, { 30, 177, 4, 3187, 8 },
            { 30, 98, 188, 2147483647, 12 }, { 30, 133, 32, 6501, 5 }, { 30, 173, 36, 7252, 19 },
            { 30, 153, 676, 2147483647, 18 }, { 30, 128, 67, 9903, 11 },
            { 30, 175, 750, 2147483647, 6 }, { 30, 56, 958, 2147483647, 3 },
            { 138, 172, 412, 2147483647, 20 }, { 138, 151, 288, 2147483647, 20 },
            { 138, 145, 62, 6392, 12 }, { 138, 165, 443, 2147483647, 3 },
            { 138, 70, 599, 2147483647, 16 }, { 138, 62, 177, 2147483647, 13 },
            { 138, 116, 5, 1756, 17 }, { 138, 102, 19, 5047, 19 }, { 138, 147, 50, 6978, 5 },
            { 138, 198, 5, 4165, 6 }, { 138, 188, 698, 2147483647, 3 },
            { 138, 132, 222, 2147483647, 14 }, { 138, 95, 902, 2147483647, 17 },
            { 138, 190, 22, 4589, 4 }, { 138, 195, 766, 2147483647, 13 },
            { 138, 168, 390, 2147483647, 6 }, { 31, 90, 1, 11, 16 },
            { 31, 170, 290, 2147483647, 8 }, { 31, 94, 108, 2147483647, 12 },
            { 31, 132, 25, 2147483647, 7 }, { 31, 120, 274, 2147483647, 18 },
            { 31, 127, 880, 2147483647, 16 }, { 31, 57, 660, 2147483647, 17 },
            { 31, 68, 311, 2147483647, 8 }, { 31, 172, 49, 4949, 3 },
            { 31, 134, 907, 2147483647, 16 }, { 31, 77, 1, 435, 12 },
            { 31, 65, 793, 2147483647, 17 }, { 31, 143, 132, 2147483647, 1 },
            { 31, 98, 31, 6956, 11 }, { 75, 157, 953, 2147483647, 10 },
            { 75, 162, 552, 2147483647, 7 }, { 75, 102, 33, 8542, 12 }, { 75, 117, 22, 3753, 1 },
            { 75, 183, 19, 3768, 4 }, { 75, 73, 34, 5038, 5 }, { 75, 58, 17, 9920, 8 },
            { 90, 166, 433, 2147483647, 20 }, { 90, 96, 936, 2147483647, 6 },
            { 90, 168, 987, 2147483647, 4 }, { 90, 110, 71, 9957, 14 }, { 90, 190, 7, 3781, 12 },
            { 90, 54, 10, 4785, 3 }, { 90, 149, 179, 2147483647, 6 }, { 90, 60, 29, 9704, 10 },
            { 90, 165, 975, 2147483647, 7 }, { 90, 66, 38, 9206, 18 },
            { 90, 63, 298, 2147483647, 20 }, { 96, 137, 49, 2147483647, 10 },
            { 96, 54, 871, 2147483647, 2 }, { 137, 75, 1, 11, 20 }, { 137, 185, 1, 11, 2 },
            { 137, 55, 15, 7453, 18 }, { 137, 168, 17, 2456, 8 }, { 137, 199, 39, 7134, 13 },
            { 137, 111, 883, 2147483647, 20 }, { 137, 78, 391, 2147483647, 3 },
            { 137, 58, 694, 2147483647, 16 }, { 137, 181, 261, 2147483647, 13 },
            { 137, 172, 56, 6264, 8 }, { 137, 177, 111, 2147483647, 1 },
            { 32, 102, 7, 2147483647, 20 }, { 32, 125, 640, 2147483647, 4 },
            { 102, 125, 1, 13, 18 }, { 102, 191, 12, 1793, 4 }, { 102, 94, 162, 2147483647, 18 },
            { 125, 187, 604, 2147483647, 9 }, { 125, 195, 363, 2147483647, 20 },
            { 125, 181, 1, 58, 15 }, { 125, 92, 86, 8762, 18 }, { 125, 77, 44, 5257, 11 },
            { 125, 70, 173, 2147483647, 8 }, { 125, 196, 914, 2147483647, 17 },
            { 125, 119, 34, 9218, 8 }, { 125, 132, 23, 6566, 17 }, { 125, 65, 53, 5513, 6 },
            { 125, 143, 8, 3469, 7 }, { 125, 179, 876, 2147483647, 9 },
            { 125, 66, 734, 2147483647, 4 }, { 125, 133, 784, 2147483647, 11 },
            { 125, 142, 575, 2147483647, 20 }, { 125, 150, 1, 196, 12 }, { 125, 81, 5, 1255, 19 },
            { 33, 103, 1, 33, 8 }, { 33, 70, 988, 2147483647, 13 }, { 33, 191, 618, 2147483647, 2 },
            { 33, 82, 870, 2147483647, 20 }, { 33, 173, 612, 2147483647, 3 },
            { 33, 100, 502, 2147483647, 9 }, { 33, 61, 296, 2147483647, 10 },
            { 33, 56, 428, 2147483647, 9 }, { 103, 152, 1, 33, 12 }, { 103, 158, 1, 33, 20 },
            { 103, 68, 4, 8392, 5 }, { 103, 189, 539, 2147483647, 7 }, { 103, 124, 9, 1626, 9 },
            { 103, 155, 132, 2147483647, 7 }, { 103, 83, 50, 6426, 8 }, { 103, 92, 51, 5812, 7 },
            { 103, 140, 35, 5186, 16 }, { 103, 69, 31, 6988, 17 }, { 103, 78, 685, 2147483647, 4 },
            { 103, 181, 3, 3565, 1 }, { 34, 88, 1, 30, 14 }, { 34, 190, 821, 2147483647, 1 },
            { 34, 80, 723, 2147483647, 15 }, { 34, 136, 5, 1159, 8 }, { 34, 71, 6, 2508, 9 },
            { 34, 62, 52, 2147483647, 20 }, { 34, 76, 1, 3246, 19 }, { 34, 174, 12, 4363, 4 },
            { 34, 75, 9, 1971, 2 }, { 34, 185, 39, 8158, 18 }, { 34, 132, 1, 1058, 10 },
            { 34, 127, 191, 2147483647, 16 }, { 34, 90, 903, 2147483647, 7 },
            { 34, 65, 42, 7835, 5 }, { 88, 197, 297, 2147483647, 20 }, { 88, 187, 1, 30, 20 },
            { 88, 57, 37, 8477, 8 }, { 88, 165, 46, 5275, 15 }, { 88, 188, 610, 2147483647, 2 },
            { 88, 179, 367, 2147483647, 12 }, { 88, 127, 646, 2147483647, 6 },
            { 88, 123, 331, 2147483647, 20 }, { 88, 59, 61, 9111, 5 },
            { 88, 146, 398, 2147483647, 7 }, { 88, 77, 56, 9765, 17 }, { 88, 192, 57, 8343, 9 },
            { 88, 148, 33, 6096, 17 }, { 35, 99, 1, 21, 20 }, { 35, 196, 24, 7424, 15 },
            { 35, 134, 3, 600, 12 }, { 35, 88, 157, 2147483647, 7 }, { 35, 101, 72, 9024, 12 },
            { 99, 182, 1, 21, 11 }, { 99, 156, 1, 21, 20 }, { 99, 189, 20, 5173, 9 },
            { 99, 72, 5, 1573, 17 }, { 99, 104, 245, 2147483647, 19 }, { 99, 89, 35, 8314, 14 },
            { 99, 143, 127, 2147483647, 19 }, { 36, 55, 1, 9, 20 },
            { 36, 153, 517, 2147483647, 15 }, { 36, 109, 59, 8616, 9 }, { 36, 169, 77, 8475, 20 },
            { 36, 93, 715, 2147483647, 15 }, { 55, 170, 1, 9, 20 }, { 55, 157, 1, 9, 20 },
            { 55, 102, 32, 3970, 19 }, { 37, 74, 603, 2147483647, 20 }, { 37, 89, 15, 3377, 11 },
            { 37, 106, 5, 1567, 20 }, { 37, 171, 248, 2147483647, 4 },
            { 37, 139, 127, 2147483647, 18 }, { 37, 53, 6, 8252, 11 }, { 37, 93, 86, 8678, 12 },
            { 37, 180, 436, 2147483647, 17 }, { 37, 192, 737, 2147483647, 17 },
            { 37, 54, 11, 8707, 5 }, { 37, 198, 733, 2147483647, 7 },
            { 37, 88, 320, 2147483647, 20 }, { 37, 124, 474, 2147483647, 11 },
            { 37, 130, 2, 4507, 15 }, { 37, 100, 12, 2573, 13 }, { 37, 146, 24, 9339, 16 },
            { 74, 187, 702, 2147483647, 20 }, { 74, 175, 659, 2147483647, 2 },
            { 74, 84, 36, 4805, 3 }, { 74, 190, 592, 2147483647, 2 },
            { 74, 55, 725, 2147483647, 1 }, { 74, 166, 596, 2147483647, 14 },
            { 74, 104, 587, 2147483647, 11 }, { 74, 178, 3, 521, 13 }, { 74, 120, 72, 9257, 11 },
            { 74, 158, 731, 2147483647, 13 }, { 74, 64, 24, 3850, 11 },
            { 74, 87, 653, 2147483647, 17 }, { 74, 156, 416, 2147483647, 11 },
            { 38, 78, 1, 21, 20 }, { 38, 127, 640, 2147483647, 3 },
            { 38, 187, 503, 2147483647, 16 }, { 38, 107, 24, 10000, 2 },
            { 38, 196, 442, 2147483647, 1 }, { 38, 60, 9, 6732, 3 },
            { 38, 176, 155, 2147483647, 14 }, { 38, 70, 555, 2147483647, 14 },
            { 38, 146, 10, 2438, 11 }, { 38, 190, 848, 2147483647, 18 },
            { 38, 180, 644, 2147483647, 14 }, { 38, 98, 46, 4601, 1 },
            { 78, 109, 731, 2147483647, 20 }, { 78, 64, 332, 2147483647, 3 },
            { 78, 133, 108, 2147483647, 7 }, { 78, 196, 16, 5150, 2 }, { 78, 114, 80, 8642, 17 },
            { 78, 73, 55, 6334, 8 }, { 78, 69, 19, 9419, 12 }, { 78, 92, 890, 2147483647, 7 },
            { 78, 98, 774, 2147483647, 9 }, { 78, 130, 36, 6074, 6 }, { 109, 118, 1, 21, 20 },
            { 109, 117, 9, 2061, 1 }, { 109, 113, 493, 2147483647, 17 },
            { 109, 105, 90, 2147483647, 13 }, { 109, 71, 13, 3323, 16 },
            { 109, 190, 757, 2147483647, 11 }, { 118, 199, 690, 2147483647, 20 },
            { 118, 168, 66, 2147483647, 19 }, { 118, 194, 389, 2147483647, 20 },
            { 118, 122, 19, 7315, 3 }, { 118, 91, 55, 2147483647, 13 },
            { 118, 128, 119, 2147483647, 2 }, { 118, 179, 561, 2147483647, 4 },
            { 118, 173, 64, 2147483647, 12 }, { 118, 187, 703, 2147483647, 2 },
            { 118, 151, 959, 2147483647, 11 }, { 118, 85, 636, 2147483647, 18 },
            { 118, 131, 572, 2147483647, 16 }, { 118, 153, 365, 2147483647, 11 },
            { 118, 108, 8, 4829, 12 }, { 118, 163, 2, 785, 5 }, { 118, 70, 29, 5478, 15 },
            { 118, 97, 394, 2147483647, 16 }, { 118, 175, 44, 7394, 1 },
            { 118, 73, 503, 2147483647, 14 }, { 118, 189, 704, 2147483647, 10 },
            { 118, 160, 29, 5908, 1 }, { 39, 111, 169, 2147483647, 3 },
            { 39, 55, 292, 2147483647, 8 }, { 39, 91, 401, 2147483647, 17 },
            { 39, 57, 44, 5133, 8 }, { 39, 126, 749, 2147483647, 8 },
            { 39, 148, 118, 2147483647, 11 }, { 39, 82, 938, 2147483647, 19 },
            { 39, 97, 21, 2655, 20 }, { 39, 83, 88, 2147483647, 15 }, { 39, 163, 37, 4624, 15 },
            { 39, 78, 22, 3255, 8 }, { 39, 104, 597, 2147483647, 3 }, { 39, 131, 28, 8143, 11 },
            { 39, 103, 8, 7183, 9 }, { 39, 136, 552, 2147483647, 12 }, { 39, 99, 17, 3783, 6 },
            { 39, 105, 146, 2147483647, 1 }, { 111, 168, 546, 2147483647, 15 },
            { 111, 155, 161, 2147483647, 19 }, { 111, 105, 181, 2147483647, 15 },
            { 111, 180, 18, 2193, 19 }, { 111, 97, 268, 2147483647, 14 }, { 111, 87, 14, 2329, 18 },
            { 111, 82, 222, 2147483647, 17 }, { 111, 160, 10, 3608, 5 },
            { 111, 89, 783, 2147483647, 4 }, { 111, 98, 15, 7511, 10 },
            { 111, 133, 35, 2147483647, 16 }, { 111, 199, 1, 2862, 13 }, { 111, 58, 49, 7107, 16 },
            { 111, 72, 415, 2147483647, 14 }, { 111, 173, 66, 2147483647, 15 },
            { 40, 116, 1, 20, 20 }, { 40, 145, 891, 2147483647, 17 }, { 40, 160, 25, 3800, 10 },
            { 40, 187, 41, 4447, 15 }, { 40, 84, 72, 9245, 17 }, { 40, 169, 39, 6851, 9 },
            { 40, 170, 9, 1141, 11 }, { 40, 86, 917, 2147483647, 2 }, { 40, 71, 5, 1024, 12 },
            { 40, 94, 681, 2147483647, 5 }, { 40, 133, 48, 2147483647, 20 },
            { 40, 105, 709, 2147483647, 1 }, { 40, 139, 778, 2147483647, 8 },
            { 40, 101, 49, 5745, 13 }, { 40, 78, 31, 3333, 6 }, { 40, 137, 996, 2147483647, 14 },
            { 40, 128, 439, 2147483647, 1 }, { 116, 194, 324, 2147483647, 20 },
            { 116, 197, 860, 2147483647, 6 }, { 116, 69, 1, 1348, 13 }, { 116, 153, 72, 9550, 1 },
            { 116, 123, 2, 4125, 5 }, { 116, 68, 676, 2147483647, 3 },
            { 116, 144, 177, 2147483647, 4 }, { 116, 141, 27, 9845, 10 }, { 116, 120, 53, 7325, 9 },
            { 116, 139, 919, 2147483647, 16 }, { 116, 60, 33, 6642, 10 },
            { 116, 157, 43, 6755, 19 }, { 116, 98, 40, 9414, 7 }, { 116, 171, 556, 2147483647, 14 },
            { 116, 72, 12, 1500, 3 }, { 116, 136, 32, 6735, 8 }, { 116, 64, 269, 2147483647, 11 },
            { 41, 149, 289, 2147483647, 20 }, { 41, 111, 673, 2147483647, 9 },
            { 41, 98, 7, 2077, 19 }, { 41, 59, 495, 2147483647, 16 }, { 41, 101, 1, 65, 19 },
            { 149, 174, 57, 2147483647, 20 }, { 149, 156, 23, 2147483647, 2 },
            { 149, 98, 516, 2147483647, 1 }, { 149, 126, 830, 2147483647, 6 },
            { 149, 122, 9, 5264, 12 }, { 149, 106, 16, 1759, 1 }, { 149, 194, 494, 2147483647, 5 },
            { 149, 186, 31, 3577, 2 }, { 149, 89, 34, 6530, 12 }, { 149, 75, 257, 2147483647, 15 },
            { 149, 180, 49, 2147483647, 14 }, { 149, 143, 98, 2147483647, 3 },
            { 149, 78, 514, 2147483647, 8 }, { 149, 178, 274, 2147483647, 11 },
            { 149, 95, 25, 8987, 16 }, { 149, 87, 868, 2147483647, 13 }, { 149, 90, 21, 7688, 9 },
            { 42, 145, 703, 2147483647, 17 }, { 42, 129, 327, 2147483647, 14 },
            { 42, 72, 488, 2147483647, 1 }, { 42, 158, 469, 2147483647, 7 },
            { 83, 159, 887, 2147483647, 18 }, { 83, 151, 87, 2147483647, 19 },
            { 83, 131, 306, 2147483647, 3 }, { 83, 79, 4, 2147483647, 17 },
            { 83, 113, 596, 2147483647, 18 }, { 83, 58, 60, 6646, 12 }, { 145, 83, 1, 13, 18 },
            { 145, 73, 517, 2147483647, 14 }, { 145, 170, 4, 626, 5 }, { 145, 200, 41, 4028, 7 },
            { 43, 113, 1, 19, 6 }, { 43, 63, 623, 2147483647, 16 }, { 43, 75, 9, 3437, 11 },
            { 43, 158, 16, 8955, 8 }, { 113, 186, 1, 19, 20 }, { 113, 188, 1, 19, 3 },
            { 113, 77, 34, 6088, 20 }, { 113, 146, 241, 2147483647, 17 },
            { 113, 191, 305, 2147483647, 6 }, { 113, 117, 18, 7265, 15 }, { 113, 68, 35, 4778, 3 },
            { 113, 122, 13, 2147483647, 8 }, { 113, 75, 42, 2147483647, 1 },
            { 113, 167, 39, 3958, 18 }, { 113, 139, 9, 2940, 17 }, { 113, 138, 23, 5165, 12 },
            { 113, 57, 18, 2486, 9 }, { 113, 112, 969, 2147483647, 10 },
            { 113, 129, 21, 2147483647, 5 }, { 113, 81, 693, 2147483647, 1 },
            { 113, 102, 53, 7582, 16 }, { 113, 115, 325, 2147483647, 11 },
            { 44, 141, 196, 2147483647, 18 }, { 44, 136, 110, 2147483647, 4 },
            { 44, 102, 20, 9448, 20 }, { 44, 191, 401, 2147483647, 19 }, { 44, 147, 6, 750, 2 },
            { 44, 186, 32, 4029, 15 }, { 44, 122, 353, 2147483647, 13 },
            { 44, 51, 669, 2147483647, 9 }, { 80, 169, 21, 2147483647, 5 }, { 80, 92, 8, 2227, 15 },
            { 80, 136, 12, 9247, 15 }, { 80, 148, 376, 2147483647, 5 },
            { 80, 79, 297, 2147483647, 13 }, { 80, 127, 655, 2147483647, 5 },
            { 80, 179, 74, 2147483647, 8 }, { 80, 87, 3, 8558, 17 },
            { 80, 171, 137, 2147483647, 10 }, { 80, 156, 88, 2147483647, 18 },
            { 80, 155, 409, 2147483647, 20 }, { 141, 144, 1, 36, 20 }, { 141, 153, 1, 36, 20 },
            { 141, 190, 536, 2147483647, 5 }, { 141, 108, 1, 19, 4 },
            { 141, 115, 878, 2147483647, 13 }, { 141, 161, 292, 2147483647, 3 },
            { 141, 184, 8, 4494, 4 }, { 141, 58, 824, 2147483647, 19 },
            { 141, 183, 929, 2147483647, 11 }, { 141, 76, 972, 2147483647, 4 },
            { 141, 189, 536, 2147483647, 5 }, { 141, 86, 26, 9260, 11 },
            { 141, 120, 868, 2147483647, 7 }, { 144, 80, 999, 2147483647, 20 },
            { 144, 162, 656, 2147483647, 17 }, { 144, 97, 53, 2147483647, 3 },
            { 144, 86, 11, 4919, 3 }, { 144, 158, 47, 5225, 3 }, { 144, 171, 29, 6795, 1 },
            { 144, 139, 936, 2147483647, 1 }, { 144, 133, 329, 2147483647, 5 },
            { 144, 51, 770, 2147483647, 14 }, { 144, 73, 266, 2147483647, 14 },
            { 45, 91, 1, 11, 20 }, { 45, 168, 349, 2147483647, 11 }, { 45, 142, 28, 2868, 7 },
            { 45, 157, 551, 2147483647, 4 }, { 45, 67, 56, 5751, 11 },
            { 45, 178, 422, 2147483647, 20 }, { 45, 189, 31, 3738, 2 }, { 45, 87, 48, 9568, 13 },
            { 91, 131, 1, 11, 10 }, { 91, 130, 882, 2147483647, 18 },
            { 91, 103, 500, 2147483647, 1 }, { 91, 185, 796, 2147483647, 20 },
            { 91, 191, 880, 2147483647, 3 }, { 91, 86, 11, 2549, 13 },
            { 131, 178, 723, 2147483647, 5 }, { 131, 188, 165, 2147483647, 11 },
            { 131, 172, 352, 2147483647, 20 }, { 131, 64, 10, 2758, 8 }, { 131, 56, 15, 9576, 17 },
            { 131, 88, 792, 2147483647, 14 }, { 131, 147, 266, 2147483647, 5 },
            { 46, 120, 1, 23, 20 }, { 46, 183, 180, 2147483647, 17 }, { 46, 155, 31, 6775, 9 },
            { 46, 192, 217, 2147483647, 19 }, { 46, 127, 207, 2147483647, 19 },
            { 46, 184, 4, 853, 15 }, { 46, 139, 937, 2147483647, 3 }, { 46, 151, 6, 571, 20 },
            { 46, 150, 439, 2147483647, 4 }, { 46, 104, 23, 2822, 8 }, { 46, 176, 4, 2547, 1 },
            { 46, 148, 478, 2147483647, 14 }, { 46, 105, 2, 105, 6 }, { 46, 103, 31, 8875, 8 },
            { 46, 197, 719, 2147483647, 5 }, { 46, 110, 29, 4129, 3 },
            { 59, 112, 279, 2147483647, 20 }, { 59, 173, 1, 23, 8 },
            { 59, 90, 415, 2147483647, 19 }, { 59, 142, 18, 9159, 15 }, { 59, 166, 69, 9704, 10 },
            { 59, 116, 420, 2147483647, 19 }, { 59, 178, 5, 6707, 14 }, { 59, 109, 15, 1461, 19 },
            { 59, 106, 65, 8261, 10 }, { 59, 70, 868, 2147483647, 13 }, { 112, 179, 1, 23, 19 },
            { 112, 125, 13, 2147483647, 4 }, { 112, 57, 13, 4341, 17 },
            { 112, 158, 919, 2147483647, 14 }, { 112, 59, 373, 2147483647, 2 },
            { 112, 155, 49, 2147483647, 17 }, { 120, 59, 1, 23, 20 },
            { 120, 190, 501, 2147483647, 19 }, { 120, 151, 18, 4559, 20 },
            { 120, 75, 931, 2147483647, 10 }, { 120, 73, 5, 681, 8 },
            { 120, 58, 798, 2147483647, 4 }, { 120, 188, 360, 2147483647, 16 },
            { 120, 123, 898, 2147483647, 16 }, { 120, 108, 18, 2306, 9 }, { 120, 175, 7, 6384, 13 },
            { 120, 128, 537, 2147483647, 12 }, { 120, 69, 603, 2147483647, 8 },
            { 47, 146, 1, 19, 20 }, { 47, 127, 160, 2147483647, 20 }, { 47, 114, 56, 5536, 20 },
            { 47, 79, 68, 2147483647, 9 }, { 47, 129, 716, 2147483647, 4 }, { 47, 95, 14, 2549, 1 },
            { 47, 54, 100, 2147483647, 16 }, { 47, 117, 2, 3322, 5 }, { 47, 141, 10, 4284, 18 },
            { 47, 175, 5, 1379, 19 }, { 146, 170, 1, 19, 13 }, { 146, 192, 1, 19, 20 },
            { 146, 135, 12, 2798, 12 }, { 146, 152, 370, 2147483647, 1 }, { 146, 140, 72, 7940, 6 },
            { 146, 145, 53, 8273, 10 }, { 146, 164, 18, 2147483647, 1 },
            { 146, 73, 690, 2147483647, 13 }, { 146, 99, 46, 4805, 1 }, { 146, 186, 39, 4006, 5 },
            { 146, 61, 13, 9031, 18 }, { 146, 180, 2, 498, 15 }, { 146, 168, 4, 2531, 14 },
            { 146, 72, 37, 6218, 20 }, { 48, 132, 879, 2147483647, 2 }, { 48, 84, 7, 661, 1 },
            { 48, 139, 174, 2147483647, 16 }, { 48, 126, 6, 1809, 8 }, { 48, 143, 86, 9131, 13 },
            { 132, 189, 1, 4, 18 }, { 132, 190, 322, 2147483647, 20 },
            { 132, 98, 839, 2147483647, 15 }, { 132, 155, 601, 2147483647, 16 },
            { 132, 164, 67, 8467, 11 }, { 132, 70, 31, 9018, 11 }, { 132, 184, 309, 2147483647, 3 },
            { 132, 153, 82, 8883, 19 }, { 132, 86, 1, 887, 11 }, { 49, 64, 342, 2147483647, 20 },
            { 49, 182, 3, 432, 5 }, { 64, 67, 198, 2147483647, 2 }, { 64, 176, 1, 7, 20 },
            { 64, 169, 44, 5750, 16 }, { 64, 73, 111, 2147483647, 1 },
            { 64, 182, 670, 2147483647, 5 }, { 64, 90, 374, 2147483647, 18 }, { 67, 157, 1, 7, 19 },
            { 67, 149, 356, 2147483647, 4 }, { 67, 194, 38, 8224, 11 },
            { 67, 104, 651, 2147483647, 7 }, { 67, 155, 55, 6497, 16 },
            { 67, 98, 416, 2147483647, 9 }, { 67, 189, 913, 2147483647, 6 },
            { 67, 162, 931, 2147483647, 18 }, { 67, 144, 297, 2147483647, 20 },
            { 67, 78, 30, 7754, 12 }, { 67, 148, 69, 7196, 3 }, { 67, 131, 4, 345, 18 },
            { 67, 186, 32, 4220, 9 }, { 50, 124, 995, 2147483647, 20 },
            { 50, 157, 94, 2147483647, 19 }, { 50, 183, 15, 6941, 6 },
            { 50, 76, 9, 2147483647, 18 }, { 50, 162, 43, 2147483647, 3 },
            { 100, 182, 251, 2147483647, 4 }, { 100, 155, 35, 3966, 11 },
            { 100, 99, 990, 2147483647, 10 }, { 100, 95, 186, 2147483647, 18 },
            { 100, 161, 50, 8035, 19 }, { 100, 149, 28, 8583, 18 },
            { 100, 148, 186, 2147483647, 9 }, { 100, 154, 197, 2147483647, 5 },
            { 100, 128, 171, 2147483647, 10 }, { 100, 112, 39, 9086, 5 }, { 100, 102, 10, 3342, 9 },
            { 100, 153, 594, 2147483647, 11 }, { 100, 192, 635, 2147483647, 6 },
            { 100, 184, 351, 2147483647, 19 }, { 100, 104, 61, 7477, 9 },
            { 100, 110, 990, 2147483647, 17 }, { 100, 74, 14, 1894, 12 },
            { 100, 108, 539, 2147483647, 15 }, { 100, 89, 141, 2147483647, 8 },
            { 124, 100, 1, 26, 15 }, { 124, 198, 629, 2147483647, 9 },
            { 124, 163, 22, 2147483647, 8 }, };
        test(testCase, 4610258);
    }

    private void test(int[][] testCase, double cost)
    {
        Graph<Integer, DefaultWeightedEdge> graph =
            new DefaultDirectedWeightedGraph<>(DefaultWeightedEdge.class);
        Map<Integer, Integer> supplyMap = new HashMap<>();
        Map<DefaultWeightedEdge, Integer> lowerMap = new HashMap<>();
        Map<DefaultWeightedEdge, Integer> upperMap = new HashMap<>();
        for (int[] data : testCase) {
            if (data.length == 2) {
                // this is information about a supply of a node
                graph.addVertex(data[0]);
                supplyMap.put(data[0], data[1]);
            } else {
                // this is information about an edge
                DefaultWeightedEdge edge =
                    Graphs.addEdgeWithVertices(graph, data[0], data[1], data[4]);
                lowerMap.put(edge, data[2]);
                upperMap.put(edge, data[3]);
            }
        }
        MinimumCostFlowProblem<Integer,
            DefaultWeightedEdge> problem = new MinimumCostFlowProblem.MinimumCostFlowProblemImpl<>(
                graph, v -> supplyMap.getOrDefault(v, 0), upperMap::get,
                e -> lowerMap.getOrDefault(e, 0));
        CapacityScalingMinimumCostFlow<Integer, DefaultWeightedEdge> minimumCostFlowAlgorithm =
            new CapacityScalingMinimumCostFlow<>(scalingFactor);
        MinimumCostFlow<DefaultWeightedEdge> minimumCostFlow =
            minimumCostFlowAlgorithm.getMinimumCostFlow(problem);
        assertEquals(cost, minimumCostFlow.getCost(), EPS);
        assertTrue(minimumCostFlowAlgorithm.testOptimality(EPS));

        assertTrue(
            checkFlowAndDualSolution(
                minimumCostFlowAlgorithm.getDualSolution(), minimumCostFlow, problem));
    }

    private <V, E> boolean checkFlowAndDualSolution(
        Map<V, Double> dualVariables, MinimumCostFlow<E> flow, MinimumCostFlowProblem<V, E> problem)
    {
        Graph<V, E> graph = problem.getGraph();
        // check supply constraints
        for (V vertex : graph.vertexSet()) {
            int supply = problem.getNodeSupply().apply(vertex);
            int flowIn = 0;
            for (E edge : graph.incomingEdgesOf(vertex)) {
                flowIn += flow.getFlow(edge);
            }
            int flowOut = 0;
            for (E edge : graph.outgoingEdgesOf(vertex)) {
                flowOut += flow.getFlow(edge);
            }
            if (supply != flowOut - flowIn) {
                return false;
            }
        }
        // check capacity constraints
        for (E edge : graph.edgeSet()) {
            if (problem.getArcCapacityLowerBounds().apply(edge) > flow.getFlow(edge)
                || problem.getArcCapacityUpperBounds().apply(edge) < flow.getFlow(edge))
            {
                return false;
            }
        }
        for (Map.Entry<E, Double> entry : flow.getFlowMap().entrySet()) {
            E edge = entry.getKey();
            if (entry.getValue() < problem.getArcCapacityUpperBounds().apply(edge)) {
                // non-negative flow on arc => have to check reduced cost optimality conditions
                if (graph.getEdgeWeight(edge) + dualVariables.get(graph.getEdgeTarget(edge))
                    - dualVariables.get(graph.getEdgeSource(edge)) < -EPS)
                {
                    return false;
                }
            }
        }
        return true;
    }
}
