public static int countWordFrequence() {
        Scanner in = new Scanner(System.in);
        HashMap<String, Integer> wordMap = new HashMap<>();
        int num = Integer.parseInt(in.nextLine());
        String input = null;
        for (int i = 0; i < num; i++) {
            input = in.nextLine();
            Integer count = wordMap.get(input);
            if (count == null)
                wordMap.put(input, 1);
            else
                wordMap.put(input, count + 1);
        }
        int count = 0;
        for (Integer wordCount : wordMap.values()) {
            double frequence = ((double) wordCount) / num;
            if (frequence >= 0.01)
                count++;
        }
        return count;
    }

    public static int testCount() {
        Scanner in = new Scanner(System.in);
        int[] testCount = new int[5];
        for (int i = 0; i < 5; i++) {
            testCount[i] = in.nextInt();
        }

        int sum = 0;
        for (int i = 0; i < testCount.length; i++) {
            int x, y, z;
            for (x = 0; x < 2; x++) {
                if (testCount[x] > 0)
                    break;
            }

            for (y = 1; y < 4; y++) {
                if (x != y && testCount[y] > 0) {
                    break;
                }
            }

            for (z = 3; z < 5; z++) {
                if (z != y && testCount[z] > 0) {
                    break;
                }
            }
            if (minus(testCount, x, y, z >= 5 ? 4 : z))
                sum++;
        }
        return sum;
    }

    private static boolean minus(int[] testCount, int x, int y, int z) {
        if (testCount[x] <= 0) {
            return false;
        }
        testCount[x]--;
        if (testCount[y] <= 0) {
            return false;
        }
        testCount[y]--;

        if (testCount[z] <= 0) {
            return false;
        }
        testCount[z]--;
        return true;
    }

    private static final int[] floor = new int[]{1, 3};

    public static int countFloorTimes(int n) {
        int[] countTimes = new int[n + 1];
        countTimes[0] = 1;
        for (int floorNum : floor) {
            for (int j = floorNum; j <= n; j++) {
                countTimes[j] = (countTimes[j] + countTimes[j - floorNum]) % 10007;
            }
        }
        return (n > 3 ? (countTimes[n] * 2 * 3 + 1) : (countTimes[n] * 2)) % 10007;
    }

    static class Direction implements Comparable<Direction> {
        int from;
        int to;

        public Direction(int from, int to) {
            this.from = from;
            this.to = to;
        } @Override public int compareTo(Direction o) {
            return to - o.to;
        }
    }

    public static int countProfesserTime() {
        int sum = 0;

        int[][] map;
        Scanner in = new Scanner(System.in);
        Direction[] directions;
        int num, count;
        num = in.nextInt();
        count = in.nextInt();
        map = new int[num + 1][num + 1];
        directions = new Direction[count];
        for (int i = 0; i < count; i++) {
            int x = in.nextInt();
            int y = in.nextInt();
            directions[i] = new Direction(x, y);
        }

        Arrays.sort(directions);
        for (Direction direction : directions) {
            map[direction.from][direction.to] = 1;
        }

    }

    public boolean findPath(int[][] map, Direction direction) {
        int start = direction.from;
        int end = direction.to;
        while (true) {

        }
    }