1363_B. Subsequence Hate_28579
Shubham has a binary string s. A binary string is a string containing only characters "0" and "1".

He can perform the following operation on the string any amount of times: 

  * Select an index of the string, and flip the character at that index. This means, if the character was "0", it becomes "1", and vice versa. 



A string is called good if it does not contain "010" or "101" as a subsequence — for instance, "1001" contains "101" as a subsequence, hence it is not a good string, while "1000" doesn't contain neither "010" nor "101" as subsequences, so it is a good string.

What is the minimum number of operations he will have to perform, so that the string becomes good? It can be shown that with these operations we can make any string good.

A string a is a subsequence of a string b if a can be obtained from b by deletion of several (possibly, zero or all) characters.

Input

The first line of the input contains a single integer t (1≤ t ≤ 100) — the number of test cases.

Each of the next t lines contains a binary string s (1 ≤ |s| ≤ 1000).

Output

For every string, output the minimum number of operations required to make it good.

Example

Input


7
001
100
101
010
0
1
001100


Output


0
0
1
1
0
0
2

Note

In test cases 1, 2, 5, 6 no operations are required since they are already good strings.

For the 3rd test case: "001" can be achieved by flipping the first character — and is one of the possible ways to get a good string.

For the 4th test case: "000" can be achieved by flipping the second character — and is one of the possible ways to get a good string.

For the 7th test case: "000000" can be achieved by flipping the third and fourth characters — and is one of the possible ways to get a good string.
from __future__ import division, print_function

import os, sys
from io import BytesIO, IOBase

if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip


def ii():  return int(input())


def si():  return input()


def mi():  return map(int, input().strip().split(" "))


def msi(): return map(str, input().strip().split(" "))


def li():  return list(mi())


def dmain():
    sys.setrecursionlimit(1000000)
    threading.stack_size(1024000)
    thread = threading.Thread(target=main)
    thread.start()


# from collections import deque, Counter, OrderedDict,defaultdict
# from heapq import nsmallest, nlargest, heapify,heappop ,heappush, heapreplace
# from math import log,sqrt,factorial,cos,tan,sin,radians
# from bisect import bisect,bisect_left,bisect_right,insort,insort_left,insort_right
# from decimal import *
# import threading
from itertools import permutations

# Copy 2D list  m = [x[:] for x in mark] .. Avoid Using Deepcopy

abc = 'abcdefghijklmnopqrstuvwxyz'
abd = {'a': 0, 'b': 1, 'c': 2, 'd': 3, 'e': 4, 'f': 5, 'g': 6, 'h': 7, 'i': 8, 'j': 9, 'k': 10, 'l': 11, 'm': 12,
       'n': 13, 'o': 14, 'p': 15, 'q': 16, 'r': 17, 's': 18, 't': 19, 'u': 20, 'v': 21, 'w': 22, 'x': 23, 'y': 24,
       'z': 25}
mod = 1000000007
# mod=998244353
inf = float("inf")
vow = ['a', 'e', 'i', 'o', 'u']
dx, dy = [-1, 1, 0, 0], [0, 0, 1, -1]


def getKey(item): return item[1]


def sort2(l): return sorted(l, key=getKey, reverse=True)


def d2(n, m, num): return [[num for x in range(m)] for y in range(n)]


def isPowerOfTwo(x): return (x and (not (x & (x - 1))))


def decimalToBinary(n): return bin(n).replace("0b", "")


def ntl(n): return [int(i) for i in str(n)]


def ceil(x, y):
    if x % y == 0:
        return x // y
    else:
        return x // y + 1


def powerMod(x, y, p):
    res = 1
    x %= p
    while y > 0:
        if y & 1:
            res = (res * x) % p
        y = y >> 1
        x = (x * x) % p
    return res


def gcd(x, y):
    while y:
        x, y = y, x % y
    return x


def isPrime(n):  # Check Prime Number or not
    if (n <= 1): return False
    if (n <= 3): return True
    if (n % 2 == 0 or n % 3 == 0): return False
    i = 5
    while (i * i <= n):
        if (n % i == 0 or n % (i + 2) == 0):
            return False
        i = i + 6
    return True


def read():
    sys.stdin = open('input.txt', 'r')
    sys.stdout = open('output.txt', 'w')


def main():
    for _ in range(int(input())):
        s = raw_input()

        def solve(s):

            zero = []
            one = []
            for i in range(len(s)):
                if s[i] == "0":
                    zero.append(i)
                else:
                    one.append(i)
            brr = [i for i in range(len(s))]
            if zero + one == brr or one + zero == brr:
                return 0
            else:
                ans1 = min(len(zero), len(one))
                ans2 = 0
                ans3 = 0
                for i in range(len(s)):
                    ans2 = s[:i].count("0") + s[i:].count("1")
                    ans3 = s[:i].count("1") + s[i:].count("0")
                    ans1 = min(ans1, ans2, ans3)
                return ans1

        print(solve(s))


BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

input = lambda: sys.stdin.readline().rstrip("\r\n")

# endregion


if __name__ == "__main__":
    # read()
    main()
    # dmain()

# Comment Read()

7
001
100
101
010
0
1
001100
 14
110
110011011110100111
10111101000010100
001111
0
00
0111000
1010111011110011011
11100100011101101
010100000111
1111101
000101100101111100
01001101000
0110
 18
010
100100011010
001
010101
101
1100111101101110
101100
0001100101001100
111110101100
01100
0110111100
110101
10000011001010010001
0011
00001010110100000101
11011101110
011000011101000010
1001111110001000
 14
110
110011011110100111
10111101000010100
000111
0
00
0111000
1010111011110011011
11100100011101101
010100000111
1111101
000101100101111100
01001101000
0110
 18
010
100100011010
001
010101
101
1100111101101111
101100
0001100101001100
111110101100
01100
0110111100
110101
10000011001010010001
0011
00001010110100000101
11011101110
011000011101000010
1001111110001000
 7
001
100
101
010
0
0
001100
 14
110
110011011110100111
10111101000010100
000111
0
00
0111000
1010111011110011011
10100100011101101
010100000111
1111101
000101100101111100
01001101000
0110
 18
010
100100011010
001
010101
101
1100111101101111
101100
0001100101001110
111110101100
01100
0110111100
110101
10000011001010010001
0011
00001010110100000101
11011101110
011000011101000010
1001111110001000
 7
001
100
101
000
0
0
001100
 18
010
100100011010
001
010101
101
1100111101101111
101100
0001100101001110
111010101100
01100
0110111100
110101
10000011001010010001
0011
00001010110100000101
11011101110
011000011101000010
1001111110001000
 14
110
110011011110100111
10111101000010100
000111
0
00
0111000
1010110011110011011
10100100010101101
010100000111
1111101
000101100101111100
01001101000
0110
 18
010
100100011010
001
010101
101
1100111101101111
101100
0001100101001110
111010101100
01100
0110111100
110001
10000011001010010001
0011
00001010110100000101
11011101110
011000011101000010
1001111110001000
 14
110
110011011110100111
10111101000010100
000111
0
00
0111000
1010110011110011011
10000100010101101
010100000111
1111101
000101100101111100
01001101000
0110
 18
010
100100011010
001
010101
101
1100111101101111
101100
0001100101001110
111010101100
01100
0110111100
110001
10000011001010110001
0011
00001010110100000101
11011101110
011000011101000010
1001111110001000
 7
011
100
101
000
0
0
011100
 14
110
110011011110100111
10111101000010100
000111
0
00
1111000
1010110011110011011
10000100010101101
010100000111
1111101
000101100101111100
01001101000
0110
 18
010
100100011010
001
010101
101
1100111001101111
101100
0001100101001110
111010101100
01100
0110111100
110001
10000011001010110001
0011
00001010110100000101
11011101110
011000011101000010
1001111110001000
 7
011
100
100
000
0
0
011100
 14
110
110011011110100111
10111101000010100
000111
0
00
1111000
1010110011110011011
10000100010101101
010110000111
1111101
000101100101111100
01001101000
0110
 18
000
100100011010
001
010101
101
1100111001101111
101100
0001100101001110
111010101100
01110
0110111100
110001
10000011001010110001
0011
00001010110100000101
11011101110
011000011101000010
1001111110001000
 14
100
110011011110100111
10111101000010100
000111
0
00
1111000
1010110011110011011
10000100010101100
010110000111
1111101
000101100101111100
01000101000
0110
 18
000
100100011010
001
010101
101
1100011001111111
101100
0001100101001110
111010101100
01110
0110111100
110001
10000011001010110001
0011
00001010110100000101
11011101110
011000011101000010
1001111110001000
 18
000
100100011010
001
110101
101
1100011001111111
101100
0001100101001110
111010101100
01110
0110111100
110001
10000011001010110001
0011
00001010110100000101
11011101010
011000011101000010
1001111110001000
 14
000
110011011110100111
10111101000010100
000111
0
00
1111000
1010110011110011011
10000100010101100
010110000111
1111101
000101000101111100
01000101001
0110
 14
000
110011011110100111
10111101000010100
000111
0
00
1111000
1010110011110011011
10000110010101100
010110000111
1111101
000101000101111100
01000101001
0110
 14
000
110011011110100111
10111101000010100
000111
0
00
1111010
1010110011110011011
10000110010101100
010110000111
1111101
000101000101111100
01000101001
0110
 18
000
100100011010
101
110101
101
1100011001111111
101100
0001100101001110
111010101100
01110
0110111100
111001
10000011001010110001
0001
00001010110100000101
11011101010
011000011101000010
1001111110001000
 14
000
110011011110100111
10111101000010100
000111
0
00
1011010
1010110011110011011
10000110010101100
010110000111
1111101
000101000101111100
01000101001
0110
 18
000
100100011010
101
110101
101
1100111001111111
101100
0001110101001110
111010101100
01110
0110111100
111101
10000011001010110001
0001
00001010110100000101
11011101000
011000011101000010
1001111110001000
 18
000
100100011010
101
110101
101
1100111001111111
101100
0001110101001110
111010101100
01110
0110111100
111101
10000011001010110001
0001
00001010110100000101
11011101000
011000011101000010
1001110110001000
 18
000
100100011010
101
110101
101
1100111001111111
101100
0001110101001110
111010101100
01110
0110111100
111101
10000011001010110001
0001
00001010110100000101
11011101000
011000001101000010
1001110110001000
 18
000
100100011010
101
110101
101
1100111001111111
101100
0001110101001110
111010101100
01110
0110101100
111101
10000011001010110001
0001
00001010110100000101
11011101000
011000001101000010
1001110110001000
 18
000
100100011010
101
110101
101
1100111001111111
101100
0001110101001110
101010101100
01110
0110101110
111101
10000011001010110001
0001
00001010110100000101
11011101000
011000001101000010
1001110110001000
 18
000
100100011010
101
110101
101
1100111001111111
101100
0001110101001110
101010101100
01110
0110101110
111101
10000011001010110001
0001
00001010010100000101
11011101000
011000001101000010
1001110110001000
 18
000
100100011010
001
110101
101
1100111001111111
101100
0001110101001110
101000101100
01110
0110101110
111101
10000011001010110001
0001
00001010010100000101
11011101000
011000001101000010
1001110110001000
 18
000
100100011010
101
110101
101
1100111001111111
101100
0001110101001110
101000101100
01110
0110101110
111101
10000011001010110001
0001
00001010010100000001
11011101000
011000001101000010
1001110110001000
 18
000
100100011000
101
110101
101
1100111001111111
101100
0001110101001110
101000101100
01110
0110101110
111101
10000011001010110001
0001
00001010010100000001
11011101000
011000001101000010
1001110110001000
 18
000
100100011000
101
110101
101
1100111001111111
101100
0001110101001110
101000101100
01110
0110101110
111101
10000011001010110001
0001
00001010010100000001
11011101000
011000001101000010
1011110110001000
 18
100
100100011000
101
110101
101
1100111001111111
101100
0001110101001110
001010101100
01110
0110101110
111101
10000011001010110001
0001
00001010010100000001
11011101000
011100001101000010
1011110110001000
 18
100
100100011000
100
110101
101
1100111001111111
101100
0001110101001110
001010101100
01110
0110101110
111101
10000011001010110001
0001
00001010010100000001
11011101000
011100001101000010
1011110110001000
 18
100
100100011000
100
110101
101
1100111001111111
101100
0001110101001110
001000101100
01110
0110101110
111101
10000011001010110001
0001
00001010010100000001
11011101000
011100001101000010
1011110110001000
 18
100
100100011000
100
110101
100
1100111001111111
101100
0001110101001110
001000101100
00110
0110101110
111101
10000011001010110001
0001
00001010010100000001
11011101000
011100001101000010
1011110110001000
 18
100
100100011000
100
110101
100
1100111001111111
101100
0001110101001110
001000101100
00110
0110101110
111101
10000011001010110001
0001
00001010010100000001
11011101000
011100001101000010
0011110110001000
 18
100
100100011000
101
110101
100
1100111001111111
101100
0001110101001110
001000101100
00110
0110101110
111101
10000011001010110001
0001
00001010010100000001
11011101000
011100001101000010
0011110110001000
 18
111
100100011000
101
110101
100
1100111101111111
101100
0001110101001110
001000101100
00110
0110101110
111101
10000011001011110001
0001
00001010010100000001
11011101000
011100001101000010
0011110110001000
 18
111
100000011000
101
010101
100
1100111101111111
101100
0001110101001110
001000101100
00100
0110101110
111101
10000011001011110001
0001
00001010010100000001
11011101000
011100001101000010
0011110110001000
 18
111
100000011000
101
010101
100
1100111101111111
101100
0001110101001110
001100101100
00100
0110101110
111101
10000011001011110001
0001
00001010010100000001
11011101000
011100001101000010
0011110110001000
 18
111
100000011000
101
010101
100
1100111101111111
101100
0001110101001110
001100101100
00100
0110101100
111101
10000011001011110001
0001
00011010010100000001
11011101000
011100001101000010
0011110110001000
 18
111
100000011000
101
010101
100
1100111101111111
101100
0101110101001110
001100101100
00100
0110101110
111101
10000011001011110001
0001
00011010010100000001
11011101000
011100001101000010
0011110110001000
 18
110
100000011000
101
010101
100
1100111101111111
101100
0101110101001110
001100101101
00100
0110101110
111101
10000011001011110001
0001
00011010010100000001
11011101000
011100001101000010
0011110110001000
 18
110
100000011000
101
010111
100
1100111101111111
101100
0101110101001110
001100101101
00100
0110101110
111101
10000011001011110001
0011
00011010010100000001
11011101000
011100001101000010
0011110110001000
 18
110
100000011000
101
010111
100
1100111101111111
101100
0101110101001110
001100101101
00100
0110101110
111101
10000011001011110001
0011
00011010010100000001
11011101000
011100001101000010
0011110110001100
 18
110
100000011000
100
010111
100
1100111101111111
101100
0101110101001110
001100101101
00100
0110101110
111101
10000011001011110001
0011
00011010010100000001
11011101000
011100001101000010
0011110110001100
 18
110
100000011000
100
010111
100
1100111101111111
101100
0101110101001110
001100101101
00100
0110101110
111101
10000011001011110001
0011
00111010010100000001
11011101000
011100001101000010
0011110110001100
 18
110
100000011000
100
011111
100
1100111101111111
101100
0101110101001110
001100101101
00100
0110101110
111101
10000011001011110001
0011
00111010010100000001
11011101000
011100001101000010
0011110110001100
 18
110
100000011000
100
011011
100
1100111101111111
001100
0101110101001110
001100101101
00100
0110101110
111101
10000011001011110001
0011
00111010010100000001
11011101000
011100001101000010
0011110110001100
 18
110
100000011000
100
011011
100
1100111101111111
001100
0101110101001110
001100101101
00101
0110101110
111111
10000011001011110001
0001
00111010010100000001
11011101000
011100001101000010
0011110110001100
 18
110
100000011000
110
011011
100
1100111101111111
001100
0101110101001110
001100101101
00111
0110101110
111111
10000011001011110001
0001
00111010010100000001
11011101000
011100001101000010
0011110110001100
 18
110
100000011000
010
011011
100
1100111101111111
001100
0101110101001110
001100101101
00111
0110101110
111111
10000011001011110001
0001
00111010010100000001
11011101000
011100001101000010
0011110110001100
 18
110
100000011000
010
011011
100
1100111101111111
001100
0101110101001110
001100101101
10111
0110101110
111111
10000011001011110001
0001
00111010010100000001
11011101000
011100001101000010
0011110110001100
 18
110
100000011000
010
010011
100
1100111101111111
101100
0101110101001110
001100101101
10111
0110101110
111111
10000011001011110001
0001
00111010010100000001
11011101000
011100001101000010
0011110110001100
 14
110
110011011110100111
10111101000010100
000111
0
00
0111000
1010111011110011011
10100100010101101
010100000111
1111101
000101100101111100
01001101000
0110
 7
011
100
101
000
0
0
001100
 7
011
000
101
000
0
0
001100
 18
010
100100011010
001
010101
101
1100111001101111
101100
0001100101001110
111010101100
01110
0110111100
110001
10000011001010110001
0011
00001010110100000101
11011101110
011000011101000010
1001111110001000
 7
011
100
100
100
0
0
011100
 14
100
110011011110100111
10111101000010100
000111
0
00
1111000
1010110011110011011
10000100010101101
010110000111
1111101
000101100101111100
01001101000
0110
 7
011
100
000
100
0
0
011100
 14
100
110011011110100111
10111101000010100
000111
0
00
1111000
1010110011110011011
10000100010101100
010110000111
1111101
000101100101111100
01001101000
0110
 18
000
100100011010
001
010101
101
1100011001101111
101100
0001100101001110
111010101100
01110
0110111100
110001
10000011001010110001
0011
00001010110100000101
11011101110
011000011101000010
1001111110001000
 7
011
000
000
100
0
0
011100
 7
011
000
000
110
0
0
011100
 14
000
110011011110100111
10111101000010100
000111
0
00
1111000
1010110011110011011
10000100010101100
010110000111
1111101
000101100101111100
01000101000
0110
 18
000
100100011010
001
110101
101
1100011001111111
101100
0001100101001110
111010101100
01110
0110111100
110001
10000011001010110001
0011
00001010110100000101
11011101110
011000011101000010
1001111110001000
 7
011
000
000
110
1
0
011100
 14
000
110011011110100111
10111101000010100
000111
0
00
1111000
1010110011110011011
10000100010101100
010110000111
1111101
000101100101111100
01000101001
0110
 18
000
100100011010
001
110101
101
1100011001111111
101100
0001100101001110
111010101100
01110
0110111100
111001
10000011001010110001
0011
00001010110100000101
11011101010
011000011101000010
1001111110001000
 18
000
100100011010
001
110101
101
1100011001111111
101100
0001100101001110
111010101100
01110
0110111100
111001
10000011001010110001
0001
00001010110100000101
11011101010
011000011101000010
1001111110001000
 18
000
100100011010
101
110101
101
1100011001111111
101100
0001100101001110
111010101100
01110
0110111100
111101
10000011001010110001
0001
00001010110100000101
11011101010
011000011101000010
1001111110001000
 14
000
110011011110100111
10111101000010100
000111
0
1
1011010
1010110011110011011
10000110010101100
010110000111
1111101
000101000101111100
01000101001
0110
 18
000
100100011010
101
110101
101
1100011001111111
101100
0001110101001110
111010101100
01110
0110111100
111101
10000011001010110001
0001
00001010110100000101
11011101010
011000011101000010
1001111110001000
 14
000
110011011110100111
10111101000010100
000111
1
1
1011010
1010110011110011011
10000110010101100
010110000111
1111101
000101000101111100
01000101001
0110
 18
000
100100011010
101
110101
101
1100111001111111
101100
0001110101001110
111010101100
01110
0110111100
111101
10000011001010110001
0001
00001010110100000101
11011101010
011000011101000010
1001111110001000
 14
000
110011011110100101
10111101000010100
000111
1
1
1011010
1010110011110011011
10000110010101100
010110000111
1111101
000101000101111100
01000101001
0110
 14
000
110011011110100101
10111101000010100
000111
1
1
0011010
1010110011110011011
10000110010101100
010110000111
1111101
000101000101111100
01000101001
0110
 18
000
100100011010
101
110101
101
1100111001111111
101100
0001110101001110
111010101100
01110
0110101110
111101
10000011001010110001
0001
00001010110100000101
11011101000
011000001101000010
1001110110001000
 18
000
100100011010
101
110101
101
1100111001111111
101100
0001110101001110
101000101100
01110
0110101110
111101
10000011001010110001
0001
00001010010100000101
11011101000
011000001101000010
1001110110001000
 18
000
100100011000
101
110101
101
1100111001111111
101100
0001110101001110
001000101100
01110
0110101110
111101
10000011001010110001
0001
00001010010100000001
11011101000
011000001101000010
1011110110001000
 18
000
100100011000
101
110101
101
1100111001111111
101100
0001110101001110
001000101100
01110
0110101110
111101
10000011001010110001
0001
00001010010100000001
11011101000
011100001101000010
1011110110001000
 18
100
100100011000
101
110101
101
1100111001111111
101100
0001110101001110
001000101100
01110
0110101110
111101
10000011001010110001
0001
00001010010100000001
11011101000
011100001101000010
1011110110001000
 18
100
100100011000
100
110101
101
1100111001111111
101100
0001110101001110
001000101100
00110
0110101110
111101
10000011001010110001
0001
00001010010100000001
11011101000
011100001101000010
1011110110001000
 18
100
100100011000
101
110101
100
1100111001111111
101100
0001110101001110
001000101100
00110
0110101110
111101
10000011001011110001
0001
00001010010100000001
11011101000
011100001101000010
0011110110001000
 18
110
100100011000
101
110101
100
1100111001111111
101100
0001110101001110
001000101100
00110
0110101110
111101
10000011001011110001
0001
00001010010100000001
11011101000
011100001101000010
0011110110001000
 18
111
100100011000
101
110101
100
1100111001111111
101100
0001110101001110
001000101100
00110
0110101110
111101
10000011001011110001
0001
00001010010100000001
11011101000
011100001101000010
0011110110001000
 18
111
100100011000
101
010101
100
1100111101111111
101100
0001110101001110
001000101100
00110
0110101110
111101
10000011001011110001
0001
00001010010100000001
11011101000
011100001101000010
0011110110001000
 18
111
100100011000
101
010101
100
1100111101111111
101100
0001110101001110
001000101100
00100
0110101110
111101
10000011001011110001
0001
00001010010100000001
11011101000
011100001101000010
0011110110001000
 18
111
100000011000
101
010101
100
1100111101111111
101100
0001110101001110
001100101100
00100
0110101100
111101
10000011001011110001
0001
00001010010100000001
11011101000
011100001101000010
0011110110001000
 18
111
100000011000
101
010101
100
1100111101111111
101100
0001110101001110
001100101100
00100
0110101110
111101
10000011001011110001
0001
00011010010100000001
11011101000
011100001101000010
0011110110001000
 18
110
100000011000
101
010101
100
1100111101111111
101100
0001110101001110
001100101100
00100
0110101110
111101
10000011001011110001
0001
00011010010100000001
11011101000
011100001101000010
0011110110001000
 18
110
100000011000
101
010101
100
1100111101111111
101100
0101110101001110
001100101100
00100
0110101110
111101
10000011001011110001
0001
00011010010100000001
11011101000
011100001101000010
0011110110001000
 18
110
100000011000
101
010101
100
1100111101111111
101100
0101110101001110
001100101101
00100
0110101110
111101
10000011001011110001
0011
00011010010100000001
11011101000
011100001101000010
0011110110001000
 18
110
100000011000
100
011011
100
1100111101111111
101100
0101110101001110
001100101101
00100
0110101110
111101
10000011001011110001
0011
00111010010100000001
11011101000
011100001101000010
0011110110001100
 18
110
100000011000
100
011011
100
1100111101111111
001100
0101110101001110
001100101101
00101
0110101110
111101
10000011001011110001
0011
00111010010100000001
11011101000
011100001101000010
0011110110001100

0
0
1
1
0
0
2
 0
6
4
0
0
0
1
6
6
2
1
6
4
1
 1
4
0
2
1
4
1
6
2
1
2
2
6
0
6
2
6
3
 0
6
4
0
0
0
1
6
6
2
1
6
4
1
 1
4
0
2
1
4
1
6
2
1
2
2
6
0
6
2
6
3
 0
0
1
1
0
0
2
 0
6
4
0
0
0
1
6
5
2
1
6
4
1
 1
4
0
2
1
4
1
5
2
1
2
2
6
0
6
2
6
3
 0
0
1
0
0
0
2
 1
4
0
2
1
4
1
5
3
1
2
2
6
0
6
2
6
3
 0
6
4
0
0
0
1
7
6
2
1
6
4
1
 1
4
0
2
1
4
1
5
3
1
2
1
6
0
6
2
6
3
 0
6
4
0
0
0
1
7
5
2
1
6
4
1
 1
4
0
2
1
4
1
5
3
1
2
1
7
0
6
2
6
3
 0
0
1
0
0
0
1
 0
6
4
0
0
0
0
7
5
2
1
6
4
1
 1
4
0
2
1
5
1
5
3
1
2
1
7
0
6
2
6
3
 0
0
0
0
0
0
1
 0
6
4
0
0
0
0
7
5
3
1
6
4
1
 0
4
0
2
1
5
1
5
3
1
2
1
7
0
6
2
6
3
 0
6
4
0
0
0
0
7
5
3
1
6
3
1
 0
4
0
2
1
4
1
5
3
1
2
1
7
0
6
2
6
3
 0
4
0
2
1
4
1
5
3
1
2
1
7
0
6
3
6
3
 0
6
4
0
0
0
0
7
5
3
1
5
3
1
 0
6
4
0
0
0
0
7
6
3
1
5
3
1
 0
6
4
0
0
0
1
7
6
3
1
5
3
1
 0
4
1
2
1
4
1
5
3
1
2
1
7
0
6
3
6
3
 0
6
4
0
0
0
2
7
6
3
1
5
3
1
 0
4
1
2
1
4
1
5
3
1
2
1
7
0
6
2
6
3
 0
4
1
2
1
4
1
5
3
1
2
1
7
0
6
2
6
4
 0
4
1
2
1
4
1
5
3
1
2
1
7
0
6
2
5
4
 0
4
1
2
1
4
1
5
3
1
3
1
7
0
6
2
5
4
 0
4
1
2
1
4
1
5
4
1
3
1
7
0
6
2
5
4
 0
4
1
2
1
4
1
5
4
1
3
1
7
0
5
2
5
4
 0
4
0
2
1
4
1
5
4
1
3
1
7
0
5
2
5
4
 0
4
1
2
1
4
1
5
4
1
3
1
7
0
4
2
5
4
 0
3
1
2
1
4
1
5
4
1
3
1
7
0
4
2
5
4
 0
3
1
2
1
4
1
5
4
1
3
1
7
0
4
2
5
3
 0
3
1
2
1
4
1
5
5
1
3
1
7
0
4
2
5
3
 0
3
0
2
1
4
1
5
5
1
3
1
7
0
4
2
5
3
 0
3
0
2
1
4
1
5
4
1
3
1
7
0
4
2
5
3
 0
3
0
2
0
4
1
5
4
1
3
1
7
0
4
2
5
3
 0
3
0
2
0
4
1
5
4
1
3
1
7
0
4
2
5
4
 0
3
1
2
0
4
1
5
4
1
3
1
7
0
4
2
5
4
 0
3
1
2
0
3
1
5
4
1
3
1
7
0
4
2
5
4
 0
2
1
2
0
3
1
5
4
1
3
1
7
0
4
2
5
4
 0
2
1
2
0
3
1
5
5
1
3
1
7
0
4
2
5
4
 0
2
1
2
0
3
1
5
5
1
3
1
7
0
5
2
5
4
 0
2
1
2
0
3
1
6
5
1
3
1
7
0
5
2
5
4
 0
2
1
2
0
3
1
6
4
1
3
1
7
0
5
2
5
4
 0
2
1
1
0
3
1
6
4
1
3
1
7
0
5
2
5
4
 0
2
1
1
0
3
1
6
4
1
3
1
7
0
5
2
5
5
 0
2
0
1
0
3
1
6
4
1
3
1
7
0
5
2
5
5
 0
2
0
1
0
3
1
6
4
1
3
1
7
0
6
2
5
5
 0
2
0
0
0
3
1
6
4
1
3
1
7
0
6
2
5
5
 0
2
0
1
0
3
2
6
4
1
3
1
7
0
6
2
5
5
 0
2
0
1
0
3
2
6
4
1
3
0
7
0
6
2
5
5
 0
2
0
1
0
3
2
6
4
0
3
0
7
0
6
2
5
5
 0
2
1
1
0
3
2
6
4
0
3
0
7
0
6
2
5
5
 0
2
1
1
0
3
2
6
4
1
3
0
7
0
6
2
5
5
 0
2
1
1
0
3
1
6
4
1
3
0
7
0
6
2
5
5
 0
6
4
0
0
0
1
6
6
2
1
6
4
1
 0
0
1
0
0
0
2
 0
0
1
0
0
0
2
 1
4
0
2
1
5
1
5
3
1
2
1
7
0
6
2
6
3
 0
0
0
0
0
0
1
 0
6
4
0
0
0
0
7
5
3
1
6
4
1
 0
0
0
0
0
0
1
 0
6
4
0
0
0
0
7
5
3
1
6
4
1
 0
4
0
2
1
5
1
5
3
1
2
1
7
0
6
2
6
3
 0
0
0
0
0
0
1
 0
0
0
0
0
0
1
 0
6
4
0
0
0
0
7
5
3
1
6
3
1
 0
4
0
2
1
4
1
5
3
1
2
1
7
0
6
2
6
3
 0
0
0
0
0
0
1
 0
6
4
0
0
0
0
7
5
3
1
6
3
1
 0
4
0
2
1
4
1
5
3
1
2
1
7
0
6
3
6
3
 0
4
0
2
1
4
1
5
3
1
2
1
7
0
6
3
6
3
 0
4
1
2
1
4
1
5
3
1
2
1
7
0
6
3
6
3
 0
6
4
0
0
0
2
7
6
3
1
5
3
1
 0
4
1
2
1
4
1
5
3
1
2
1
7
0
6
3
6
3
 0
6
4
0
0
0
2
7
6
3
1
5
3
1
 0
4
1
2
1
4
1
5
3
1
2
1
7
0
6
3
6
3
 0
6
4
0
0
0
2
7
6
3
1
5
3
1
 0
6
4
0
0
0
2
7
6
3
1
5
3
1
 0
4
1
2
1
4
1
5
3
1
3
1
7
0
6
2
5
4
 0
4
1
2
1
4
1
5
4
1
3
1
7
0
5
2
5
4
 0
3
1
2
1
4
1
5
4
1
3
1
7
0
4
2
5
3
 0
3
1
2
1
4
1
5
4
1
3
1
7
0
4
2
5
3
 0
3
1
2
1
4
1
5
4
1
3
1
7
0
4
2
5
3
 0
3
0
2
1
4
1
5
4
1
3
1
7
0
4
2
5
3
 0
3
1
2
0
4
1
5
4
1
3
1
7
0
4
2
5
4
 0
3
1
2
0
4
1
5
4
1
3
1
7
0
4
2
5
4
 0
3
1
2
0
4
1
5
4
1
3
1
7
0
4
2
5
4
 0
3
1
2
0
3
1
5
4
1
3
1
7
0
4
2
5
4
 0
3
1
2
0
3
1
5
4
1
3
1
7
0
4
2
5
4
 0
2
1
2
0
3
1
5
5
1
3
1
7
0
4
2
5
4
 0
2
1
2
0
3
1
5
5
1
3
1
7
0
5
2
5
4
 0
2
1
2
0
3
1
5
5
1
3
1
7
0
5
2
5
4
 0
2
1
2
0
3
1
6
5
1
3
1
7
0
5
2
5
4
 0
2
1
2
0
3
1
6
4
1
3
1
7
0
5
2
5
4
 0
2
0
1
0
3
1
6
4
1
3
1
7
0
6
2
5
5
 0
2
0
1
0
3
2
6
4
1
3
1
7
0
6
2
5
5
