#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define test(x) cout << #x << ' ' << x << endl
#define printv(x) { \
for (auto a : x) cout << a << ' '; \
cout << endl; \
}
#define pii pair<int, int>
#define pll pair<lli, lli>
#define X first
#define Y second
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
const int N = 512, abc = 864197532;
string ans[] = {"-1", "0",
"00",
"10",
"0000",
"100",
"010",
"1000",
"1100",
"0100",
"0110",
"1010",
"01000",
"00100",
"01110",
"01100",
"10100",
"10010",
"011110",
"01010",
"011000",
"101000",
"001100",
"110100",
"100100",
"101100",
"1010000",
"010100",
"010010",
"011010",
"1101000",
"1001000",
"101010",
"1011000",
"1011100",
"0101000",
"00110000",
"0100010",
"0010100",
"0100100",
"10000100",
"0110100",
"0101100",
"0110110",
"0110010",
"1010100",
"11011000",
"1010010",
"1001010",
"00101000",
"01001000",
"10011000",
"101111100",
"0101010",
"00100100",
"01011000",
"11001100",
"01011100",
"10101000",
"00110100",
"01110010",
"01100100",
"01101100",
"11010100",
"10001010",
"10100100",
"10110100",
"10010100",
"01100110",
"10101100",
"001000100",
"10110010",
"10010110",
"10011010",
"01010100",
"010111000",
"001101000",
"01010010",
"01011010",
"01101010",
"001110100",
"110101000",
"010011000",
"101001000",
"010001100",
"101101000",
"100101000",
"10101010",
"1001110000",
"100010100",
"101011000",
"110100100",
"011100110",
"101011100",
"1000011100",
"010101000",
"110010100",
"011001100",
"101100100",
"101101100",
"0110110000",
"010100010",
"100110100",
"001010100",
"101001100",
"011101010",
"010100100",
"010010100",
"1010001000",
"010110100",
"011010100",
"1010110000",
"1011101000",
"010101100",
"011011010",
"011010010",
"0101010000",
"010110010",
"1000100010",
"011001010",
"0011100100",
"101010100",
"1010111000",
"1100101000",
"0111001110",
"1011001000",
"101010010",
"101001010",
"1011100010",
"100101010",
"1011000100",
"1001101000",
"0010101000",
"0110011100",
"1001011000",
"0101001000",
"1100100100",
"0100101000",
"0101000100",
"1010001100",
"0101101000",
"0110101000",
"010101010",
"1010011100",
"0101110100",
"1100110100",
"0111010100",
"0101011000",
"10011111010",
"1001110010",
"1001100100",
"0100100100",
"0010110100",
"1001101100",
"11010110000",
"1010101000",
"0101100010",
"0011010100",
"0110100100",
"0110110100",
"10011010000",
"0101100100",
"10110000100",
"0100110100",
"0100101100",
"0110010100",
"0110110110",
"0110101100",
"1101010100",
"0101001100",
"0110010010",
"0110110010",
"01101010000",
"1010100100",
"0100110010",
"1011010100",
"1010010100",
"1010110100",
"10001011000",
"1001010100",
"10100011000",
"1010010010",
"10010111000",
"1011010010",
"1010101100",
"1001001010",
"1001010010",
"00101001000",
"00100101000",
"1001011010",
"1010110010",
"1001010110",
"1010011010",
"10100011100",
"1001101010",
"00101101000",
"01000100100",
"0101010100",
"10011000100",
"10011011000",
"10001001100",
"01101001000",
"10001100100",
"10011101100",
"01101101000",
"0101010010",
"0101001010",
"0101101010",
"01101110100",
"01001101000",
"0110101010",
"01100101000",
"01011011000",
"01001011000",
"101101110000",
"11010101000",
"01011100100",
"01101011000",
"01110110110",
"01010011000",
"10101001000",
"01110101100",
"101110001000",
"01110010100",
"10110101000",
"10100101000",
"010111010000",
"10101101000",
"01101100010",
"10010101000",
"01110010010",
"1010101010",
"01010011100",
"01100100100",
"00110010100",
"01101100100",
"10100010010",
"10001010100",
"00110101100",
"10101011000",
"11010100100",
"01001001100",
"100100110000",
"10010100010",
"01001101100",
"11010010100",
"10001010010",
"10101011100",
"10100100100",
"01100110100",
"000101101000",
"10110100100",
"01010101000",
"10101100010",
"01011001100",
"10010100100",
"10010010100",
"10100011010",
"001011101000",
"10011101010",
"100100011000",
"10101100100",
"10001101010",
"10110010100",
"10101101100",
"10110101100",
"01100110010",
"10100110100",
"01010100010",
"10011010100",
"01010001010",
"10110010010",
"10010101100",
"00101010100",
"101001010000",
"10101001100",
"110110011000",
"101011010000",
"01110101010",
"10011011010",
"10010011010",
"01010100100",
"10010110010",
"101111010100",
"01001010100",
"01010010100",
"10010100110",
"01011010100",
"01010110100",
"010010111000",
"10011001010",
"01101010100",
"001001011000",
"01010010010",
"101010110000",
"01001010010",
"011001001000",
"01011011010",
"110001101100",
"01010101100",
"01011010010",
"01101101010",
"001110110100",
"01101010010",
"010011001000",
"01101011010",
"01101001010",
"010101010000",
"011011011000",
"01010110010",
"01101010110",
"01011001010",
"010010011000",
"110100101000",
"110101101000",
"01100101010",
"101011000010",
"010011011000",
"010010001100",
"101101001000",
"10101010100",
"001110010100",
"110100010100",
"101101101000",
"100101001000",
"011010011000",
"110010101000",
"100100101000",
"001001100100",
"010110011000",
"001100100100",
"110101011000",
"101011001000",
"10101010010",
"010100001010",
"10101001010",
"10100101010",
"100101101000",
"001101101100",
"011000110100",
"011100101100",
"10010101010",
"101001101000",
"101011011000",
"100110101000",
"101011000100",
"101110101100",
"100101110100",
"0010101111000",
"001010101000",
"101110010100",
"101100010100",
"101100100010",
"100101011000",
"101000101100",
"101101011100",
"101010011000",
"010101001000",
"101001110100",
"100111010100",
"100100100100",
"110101100100",
"101001011100",
"010010101000",
"010100101000",
"010101000100",
"101010001100",
"010110101000",
"100110100010",
"010101101000",
"011011001100",
"101100100100",
"011010101000",
"010100010100",
"110010110100",
"01010101010",
"100111010010",
"010111010100",
"101001100010",
"010101110100",
"010100100010",
"110011010100",
"1010010010000",
"1101011010000",
"1101010000100",
"100110100100",
"100110001010",
"100101100100",
"010101011000",
"001010100100",
"100011001010",
"101001100100",
"100101101100",
"010110100010",
"001010010100",
"101001001100",
"101100110100",
"1100101010000",
"101101001100",
"001011010100",
"011010111010",
"010100100100",
"011010001010",
"011101011010",
"010010100100",
"010010010100",
"011101001010",
"100110101100",
"100100110110",
"101010101000",
"011101010110",
"010110100100",
"0110110111000",
"010110110100",
"001101010100",
"011010100100",
"010010010010",
"011011010100",
"1011101001000",
"1001101010000",
"011000101010",
"0100111011000",
"1010110110000",
"011010010100",
"010101100100",
"011100101010",
"0011011001000",
"0110011101000",
"010011010100",
"010101101100",
"010110010100",
"010010101100",
"010100110100",
"0101010010000",
"010110101100",
"010100101100",
"011001010100",
"1010100110000",
"1101001001000",
"101010001010",
"0101100111100",
"011010101100",
"0100101010000",
"110101010100",
"010110110010",
"1001011101000",
"010101001100",
"010011010010",
"1011000101000",
"1011101011000",
"0101011010000",
"011001001010",
"0011001101000",
"011001010010",
"011010010110",
"011010110010",
"101010100100",
"1001001001000",
"0100001010100",
"1101011001000",
"011001011010",
"101101010100",
"0101010001000",
"101010010100",
"101011010100",
"101001010100",
"010110011010",
"101010110100",
"1001011000010",
"1011100100010",
"0101011110100",
"011001101010",
"100101010100",
"1011011001000",
"0100010101000",
"1101001101000",
"101010010010",
"0101010110000",
"0110001100010",
"1100101101000",
"101101010010",
"0110011000100",
"0101110101000",
"101001010010",
"0111000110110",
"101010101100",
"0101011101000",
"1100110101000",
"100100101010",
"1001101001000",
"0110010001100",
"100101010010",
"1001011001000",
"100101001010",
"0010101001000",
"0110001100100",
"100101011010",
"100101101010",
"1010101010000",
"0111101010010",
"0100011001100",
"101010110010",
"1100101011000",
"101011001010",
"11010111010000",
"101001101010",
"0111101001010",
"1011001101000",
"00110010010000",
"0101001001000",
"0010110101000",
"100110101010",
"1001100101000",
"0100101001000",
"10010100001000",
"1011010011000",
"00100010111000",
"0100100101000",
"1010011011000",
"010101010100",
"1011001011000",
"0101000100100",
"0101101001000",
"01110011010000",
"1001010011000",
"0100010010100",
"0100100010100",
"0110101001000",
"1001101011000",
"0011010101000",
"11011010010000",
"1011010001100",
"1010110011000",
"0110110101000",
"0100101101000",
"0101101000100",
"1001100100010",
"0010101011000",
"0101110110100",
"0101011001000",
"010101010010",
"0101110100100",
"1001110101100",
"010101001010",
"010101101010",
"010110101010",
"1001110010100",
"0100110101000",
"1001000110010",
"0101100101000",
"1100101100100",
"0110011000110",
"1001110110010",
"011010101010",
"0010100100100",
"0110100010100",
"10101111001000",
"0110010101000",
"1010110001100",
"0100101011000",
"0101011000100",
"0111010010100",
"00100100011000",
"0101101011000",
"0101001011000",
"1001100100100",
"1101010101000",
"0101011100100",
"1100110010100",
"0100100100100",
"0101011011100",
"0010110100100",
"0110101011000",
"0101100010100",
"0010110110100",
"0101110010100",
"0101000110100",
"0101010011000",
"0100101011100",
"1010101001000",
"1011001100100",
"0110001010100",
"01000111000100",
"0111010101100",
"11001011010000",
"1011011001100",
"0101100010010",
"0010101100100",
"0111001010100",
"1011010101000",
"0011010100100",
"1010100101000",
"1010101000100",
"1010110101000",
"1010010101000",
"0110100100100",
"0110001001010",
"0110110100100",
"1010101101000",
"0110110110100",
"0110111001010",
"0011010010100",
"1011101010100",
"1001010101000",
"1001100110100",
"0110101100010",
"0101100100100",
"0110101110010",
"101010101010",
"0101101100100",
"1010001010100",
"1001100101100",
"0100110100100",
"0100101100100",
"1010101110100",
"0100100110100",
"1010011001100",
"0011001010100",
"0100100101100",
"1010100010010",
"0110010100100",
"0100101101100",
"01001010010000",
"0110010010100",
"0110101100100",
"1010001001010",
"0110110010100",
"0011010101100",
"10101001111000",
"1010101011000",
"0110110101100",
"1101010100100",
"0101001100100",
"1010001010010",
"10011010001000",
"1010110100010",
"11010001101000",
"0100110010100",
"0101001001100",
"0110010110100",
"0110100110100",
"1101010010100",
"00010100101000",
"10010100110000",
"0110110110010",
"0110100101100",
"1101001010100",
"0101100110100",
"11001110101000",
"1000101010010",
"1010101011100",
"1010100100100",
"0110011010100",
"1001011101010",
"01010110010000",
"0101100101100",
"0100110010010",
"1011010100100",
"0110101001100",
"1011011010100",
"00101010110000",
"1010010100100",
"01101011010000",
"0101010101000",
"1010110100100",
"1000101010110",
"1010101100010",
"1010110110100",
"0110110100110",
"1010101110010",
"1011010010100",
"1100101010100",
"1001010100100",
"00101011101000",
"1010011101010",
"1001001010100",
"0110011011010",
"01011010001000",
"0110110011010",
"10100111001000",
"10011000101000",
"1001010010100",
"1010010110100",
"0110100110010",
"00110011011000",
"0110010110010",
"00011010101000",
"1010101100100",
"1001011010100",
"1001010110100",
"11010011001000",
"0101100110010",
"01011010110000",
"1011001010100",
"01101110101000",
"1010110010100",
"1001001001010",
"01110101001000",
"1011010101100",
"1010011010100",
"1001010010010",
"1010100110100",
"10101010010000",
"0110011001010",
"10110010111000",
"1010010101100",
"1010100101100",
"1001101010100",
"01010100110000",
"01010110001000",
"11010010011000",
"0101010001010",
"1001011011010",
"0101011101010",
"01101011101000",
"1001010101100",
"1010110010010",
"1010110110010",
"0010101010100",
"1001011010010",
"1011001010010",
"01010111001000",
"10101101010000",
"1010101001100",
"10010100111000",
"1010010011010",
"01010111011000",
"10011011001000",
"10101010000100",
"10101011010000",
"1010011010010",
"1010010110010",
"1001101101010",
"01001001000100",
"10010101010000",
"1001001101010",
"1001101010010",
"10110011001000",
"01011101011000",
"0101010100100",
"01010001011000",
"1001101011010",
"01100010101000",
"1001101001010",
"01100110011000",
"1001011001010",
"00101011001000",
"0100101010100",
"1010100110010",
"10101010001000",
"0101010010100",
"0101001010100",
"10101111010100",
"0101011010100",
"0101101010100",
"01101001001000",
"01110101011000",
"0101010110100",
"01101101001000",
"00110110101000",
"01110101110110",
"10101011110100",
"00101100101000",
"1001100101010",
"00101001101000",
"0110101010100",
"01010100011000",
"00110100101000",
"10100100001010",
"01011001001000",
"10011100100100",
"0101010010010",
"00110101101000",
"10101010110000",
"01011011001000",
"0101001001010",
"10000101010100",
"0100101010010",
"00100100100100",
"0101101101010",
"0101001010010",
"01101101110100",
"00101101011000",
"01110110100100",
"01110111001010",
"0101101010010",
"0101010101100",
"0101011010010",
"00110010101000",
"10011010011000",
"0101101011010",
"0110110101010",
"10011001011000",
"0101101001010",
"01011101100100",
"01100100101000",
"0110101010010",
"10001010101000",
"00101010011000",
"01101100101000",
"0110101101010",
"0110101001010",
"01000101100100",
"0110101011010",
"01100101000100",
"0110100101010",
"11011010101000",
"01010101010000",
"00111010010100",
"01001011000100",
"11001001100100",
"01011100100100",
"0101010110010",
"01001100101000",
"00110011001100",
"0110101010110",
"0101011001010",
"01101101011000",
"0101100101010",
"11010110101000",
"01001110100100",
"01000110110100",
"01001011100100",
"01100010010100",
"01101011000100",
"11010010101000",
"10101001001000",
"11010101101000",
"0110010101010",
"01001010011000",
"01010001001100",
"10011100101100",
"01010011000100",
"01100110101000",
"10110101001000",
"01101100010100",
"01101001011000",
"01010011011000",
"01101011011100",
"10100101001000",
"01010001100100",
"1010101010100",
"10110110101000",
"10101101001000",
"01000110010100",
"00110100100100",
"10100100101000",
"10001010100010",
"01110100110100",
"01011001011000",
"00110110100100",
"01101010011000",
"01101101110010",
"10010101001000",
"10101101101000",
"10110100101000",
"01101000110100",
"11001010101000",
"10111010100100",
"10110101101000",
"01000110101100",
"10100100010100",
"10010010101000",
"01010110011000",
"10101101000100",
"11001011001100",
"10100010100100",
"10101110110100",
"01100111010100",
"10010100101000",
"11010101011000",
"01110001101010",
"10010101000100",
"10101011001000",
"011101011010000",
"1010101010010",
"01110011010100",
"00110010100100",
"10010001010100",
"10010110101000",
"1010101001010",
"1010100101010",
"10010101101000",
"1010010101010",
"10011001100100",
"10110010101000",
"01100101011100",
"10101100101000",
"10001010100100",
"01110100110110",
"10010100010100",
"00110110010100",
"01100111011010",
"10100110101000",
"101100110010000",
"01101110011010",
"1001010101010",
"10101001101000",
"00101100110100",
"11011010100100",
"01110010110110",
"11010100100100",
"10101011011000",
"10011010101000",
"10010111010100",
"10110101011000",
"10010101110100",
"10101011000100",
"01110011011010",
"10101101011000",
"01010110011100",
"10001010110100",
"10001011010100",
"10110011001100",
"10100101011000",
"10101001011000",
"00110100101100",
"00101010101000",
"11010010100100",
"10001001010010",
"010101101110000",
"11010010010100",
"100110010001000",
"00110011010100",
"10001010010010",
"10110001010100",
"10101100010100",
"10010101011000",
"10010111011010",
"10101100100010",
"10010001011010",
"10100100100100",
"01100110100100",
"10100111010100",
"10100011010100",
"10101010011000",
"01101001100100",
"01110010100110",
"01010101001000",
"01100101100100",
"101010001010000",
"01101100110100",
"10110100100100",
"10110110100100",
"10001011011010",
"01100100110100",
"10110110110100",
"01011001100100",
"101000101010000",
"10101001011100",
"11010101100100",
"01100101101100",
"10001010110110",
"10001101010100",
"01001010101000",
"11001010100100",
"10101110010010",
"01010100101000",
"10010101011100",
"01010010101000",
"11010110010100",
"10010010010100",
"01010110101000",
"01011010101000",
"01001011001100",
"01011001101100",
"111001010011000",
"10011101101010",
"11001010010100",
"01010101101000",
"11010011010100",
"01100110010100",
"011011001010000",
"10010001101010",
"010100110010000",
"01000101010100",
"101010111101000",
"01101010101000",
"101001100110000",
"10101100100100",
"01101101100110",
"01010100010100",
"10010101100010",
"10101101100100",
"10010110100100",
"0101010101010",
"10011101011010",
"10110101100100",
"10001101101010",
"10110110010100",
"10110010010100",
"10101101101100",
"10001101010010",
"10010110001010",
"011101101001000",
"01010101110100",
"110101100011000",
"10010111001010",
"10110101101100",
"10100110100100",
"11001101010100",
"10100110001010",
"10100101100100",
"10100011001010",
"110100101010000",
"01101100110010",
"10100100110100",
"10011010100100",
"01100100110010",
"01100110110010",
"110110011001000",
"01110101010100",
"010100100110000",
"10010101100100",
"01001010100010",
"10110010110100",
"11001010101100",
"10010011010100",
"011110110010100",
"01010101011000",
"01010001010010",
"10110100101100",
"00101010100100",
"10010010101100",
"01001100110010",
"10101001100100",
"10011010010100",
"011010010110000",
"110011011001000",
"10010110010100",
"01010110100010",
"10010100110100",
"10010010010110",
"010110100110000",
"01010111010010",
"10110011010100",
"110101010001000",
"00101010010100",
"10010100101100",
"10010110101100",
"10100110010100",
"10110101001100",
"00101011010100",
"01011101001010",
"011010100110000",
"10101100110100",
"10101001101100",
"00101101010100",
"10100101001100",
"01101010001010",
"10110010101100",
"10101101001100",
"01110101010010",
"01010101011100",
"01010100100100",
"10011001010100",
"10100110101100",
"01101000101010",
"10101100101100",
"10011011010010",
"10010110010010",
"10010010110010",
"10010011010010",
"01001010100100",
"101001011010000",
"10010101001100",
"01001001010100",
"01010010100100",
"010011101000100",
"110101010110000",
"01010010010100",
"10100110010010",
"001101001001000",
"10100100110010",
"10101010101000",
"10010010100110",
"10010100100110",
"01010110100100",
"01011011010100",
"01010101100010",
"10101011001100",
"10110011010010",
"01010110110100",
"001001101101000",
"01010101110010",
"011101001101000",
"010100100011000",
"00110101010100",
"10110010110010",
"01101010100100",
"01001010110100",
"10011001001010",
"001101101101000",
"01011100101010",
"01101101010100",
"01011010010100",
"10011001010010",
"01011010110100",
"101001000101000",
"01010010010010",
"10010100110010",
"01010010110100",
"011100101101000",
"01100010101010",
"10011010110010",
"001011101100100",
"01101010010100",
"01101011010100",
"011101001011000",
"101010110110000",
"011001001001000",
"111001010101000",
"101101010110000",
"01010101100100",
"01011011011010",
"01101010110100",
"10101100110010",
"101011010110000",
"10011010011010",
"011011001001000",
"101110101101000",
"101101000101000",
"011011011001000",
"01001101010100",
"101010010110000",
"10010101100110",
"01010101101100",
"01010110010100",
"10100110011010",
"01010011010100",
"100010010101000",
"01011001010100",
"011010010111000",
"011000110101000",
"001001010011000",
"01010100110100",
"101011101000100",
"01010110101100",
"01010010101100",
"01101101010010",
"10011001101010",
"01011010101100",
"10101010100010",
"01010100101100",
"011010100111100",
"01100101010100",
"01101101011010",
"101010100110000",
"101010110001000",
"01101001001010",
"001001101011000",
"01101101001010",
"10101010001010",
"010101100111100",
"10101000101010",
"010011011001000",
"01101001010010",
"01101011010010",
"01101010101100",
"100100110011000",
"100111001100010",
"01010110010010",
"010110100111000",
"11010101010100",
"010101001010000",
"01101101010110",
"100010101101000",
"010100101010000",
"100001001010110",
"01001101010010",
"01011001001010",
"01010101001100",
"010110101010000",
"110010110001100",
"110101010111000",
"01011001010010",
"01101011010110",
"01011010110010",
"001011001011000",
"01010011010010",
"01010010110010",
"010101011010000",
"010011000100100",
"011001101001000",
"10001010101010",
"01100100101010",
"010111000110100",
"01101010010110",
"010001100100100",
"011010101010000",
"01101100101010",
"01100101010010",
"101001110101000",
"01011010011010",
"001010110011000",
"101101001001000",
"01101010110010",
"10101010100100",
"100010101110100",
"101000101011000",
"01101011001010",
"101010001011000",
"011001101101000",
"01100101011010",
"011011001101000",
"01100101101010",
"01101010011010",
"110101011001000",
"01101001101010",
"011001001101000",
"10110101010100",
"01010100110010",
"110010101001000",
"010101010001000",
"100101001001000",
"10101010010100",
"01010011001010",
"10101101010100",
"10101001010100",
"10101011010100",
"01101010100110",
"10100101010100",
"011011010011000",
"011010010011000",
"010111101010100",
"110101100101000",
"10101010110100",
"110010010101000",
"1010110110100000",
"001001100100100",
"100010010111010",
"011001001011000",
"011010011000100",
"100101001000100",
"011001011011000",
"110010100101000",
"01100110101010",
"001100100100100",
"010110110011000",
"10010101010100",
"011101001100100",
"110101001101000",
"101011001001000",
"100100101000100",
"011001110100100",
"010001010101000",
"100100010100100",
"010010110011000",
"110010110101000",
"10101010010010",
"101100101001000",
"010101000101000",
"010101010110000",
"110010101101000",
"101101011001000",
"010100010101000",
"011011001110100",
"10101001001010",
"011001011100100",
"10110101010010",
"011011010001100",
"10100100101010",
"101101100101000",
"101100100101000",
"101010001110100",
"10101001010010",
"100101101101000",
"10101101010010",
"101001101001000",
"011010110011000",
"10100101010010",
"011001010011000",
"1110101101010000",
"10101010101100",
"10101011010010",
"10100101001010",
"110001001010100",
"110011010101000",
"100110101001000",
"110001010100100",
"10101101001010",
"10010010101010",
"100011101010100",
"10100101011010",
"011101101100110",
"010110001100100",
"10100101101010",
"100101011001000",
"010110011100100",
"10010101010010",
"101101101011000",
"011101010101000",
"101101110101100",
"110101010011000",
"100110110101000",
"10010100101010",
"10010101001010",
"001010101001000",
"100010010110100",
"10010101101010",
"010110110001100",
"10010101011010",
"101010011001000",
"101101011000100",
"10010110101010",
"001001010101000",
"100010100011010",
"101010101010000",
"101101110010100",
"100110100101000",
"101001001011000",
"101000100110100",
"110001010110100",
"100101100101000",
"001011001100100",
"10101010110010",
"011000110010100",
"100110101101000",
"011001101011100",
"100101001101000",
"10010101010110",
"10101011001010",
"101100110101000",
"10101001101010",
"001010010101000",
"10100110101010",
"100100101011000",
"101001100101000",
"001100101100100",
"001101001100100",
"100101011011000",
"001010110101000",
"101001110110100",
"011000100110010",
"101000110100100",
"100010011010100",
"001100100110100",
"010101001001000",
"101010010011000",
"100010101100100",
"001010101101000",
"10011010101010",
"100111010100100",
"101001011100100",
"101101000101100",
"100101001011000",
"101101010011000",
"100110010101000",
"101110010110100",
"010010101001000",
"110110010100100",
"100110101110100",
"110101100100100",
"101101101100010",
"010100101001000",
"101001010011000",
"001010100010100",
"101010011011000",
"010101001000100",
"101011010011000",
"110010100100100",
"010010010101000",
"01010101010100",
"010110101001000",
"101010010001100",
"010100100101000",
"001010111010100",
"010101101001000",
"110010010010100",
"101001101011000",
"100101100010100",
"101011001011000",
"101101001011100",
"100101000110100",
"010010100101000",
"010101010111000",
"001011101010100",
"010110110101000",
"101001110001010",
"010010101000100",
"0101011010100000",
"011001001100100",
"011010101001000",
"010100101000100",
"101101010001100",
"010101101101000",
"110100110100100",
"100110101011000",
"001101010101000",
"010100100010100",
"101100100100100",
"010010110101000",
"010011100110010",
"101101100100100",
"010110101000100",
"010010101101000",
"0100110101110000",
"010110100101000",
"101000100110010",
"101010011100100",
"0010110011010000",
"010101101000100",
"010110111010100",
"010011001100100",
"010110101101000",
"101101101101100",
"100100100111010",
"010010100010100",
"1010111101000100",
"010100101101000",
"101011100101100",
"011010100101000",
"101001100010010",
"011010101000100",
"010101011001000",
"010101110100100",
"1010101110010000",
"01010101010010",
"110101001100100",
"101010010011100",
"100101110010010",
"011010010101000",
"1001001100110000",
"011011101010100",
"110011010100100",
"01010101001010",
"01010100101010",
"01010110101010",
"010011011001100",
"100110010100010",
"01011010101010",
"010010111010100",
"110011011010100",
"010010101110100",
"010011010101000",
"100111001010100",
"010110100010100",
"010111010110100",
"010101100101000",
"011101010100100",
"010111010010100",
"0011101001001000",
"010100110101000",
"110100110010100",
"010110010101000",
"010100010110100",
"1101100100111000",
"011010100010100",
"1011010010010000",
"100101100100100",
"1000010101101000",
"01101010101010",
"010101001101000",
"100100110100100",
"001001010100100",
"110011010110100",
"001110101010100",
"001010100100100",
"100100100110100",
"010110100100010",
"1110101001001000",
"010101011011000",
"011001010101000",
"100110010111010",
"101001100100100",
"110010100110100",
"010010101011000",
"100110101100010",
"100110110001010",
"010101011000100",
"101001001100100",
"010111000101010",
"100011001010010",
"001010010100100",
"010101101011000",
"010100101011000",
"011001011001100",
"001010010010100",
"011001100101100",
"010110101011000",
"101001001001100",
"010101001011000",
"011011101010010",
"101001101100100",
"101011100110010",
"110101010101000",
"101101100110100",
"010101011100100",
"010101110101100",
"010010110100010",
"001010110100100",
"001011010100100",
"010001101010100",
"110011001010100",
"100100111001010",
"010101011011100",
"010111010101100",
"001011011010100",
"0111001001001000",
"100110010100100",
"010101000101100",
"011010101011000",
"010100100100100",
"011101010010010",
"010101110010100",
"010100011010100",
"100110010010100",
"100101001100100",
"010110001010100",
"101100100101100",
"101100101101100",
"010111001010100",
"100100110010100",
"010010100100100",
"010101010011000",
"010010101011100",
"011010001010010",
"010010010010100",
"011010111010010",
"101010101001000",
"001011010010100",
"100101001001100",
"010110010001010",
"001011010110100",
"0011100101001000",
"011000101010100",
"010011010100010",
"011101011010010",
"010110101011100",
"101011001100100",
"011101010101100",
"101001100011010",
"010110010100010",
"1101010110110000",
"1101101000101000",
"010101100010010",
"100100110101100",
"011010111010110",
"100101001101100",
"010110100100100",
"1010101010100000",
"101100110010100",
"010110110100100",
"011100101010100",
"101011011001100",
"101101010101000",
"1001100111011000",
"001101010100100",
"010100010110010",
"010110111001010",
"101010100101000",
"100110100110100",
"011101011010110",
"101010101000100",
"101011010101000",
"101010010101000",
"010101010001100",
"101010110101000",
"011011010100100",
"101001010101000",
"011001100110010",
"101100101001100",
"011011011010100",
"010010010110100",
"010110101100010",
"101001100110100",
"100101100101100",
"010100101100010",
"010111010011010",
"101010101101000",
"010111001010010",
"001101010010100",
"0010101010010000",
"001101011010100",
"100100110110010",
"101001011001100",
"0100100011011000",
"100110011010100",
"010100111010010",
"101110101010100",
"001101001010100",
"011010010100100",
"100101010101000",
"011010110100100",
"001101010110100",
"1011011010110000",
"011010010010100",
"010101100100100",
"0010010101010000",
"101010100010100",
"011010110110100",
"011011010110100",
"100101011001100",
"101011101010100",
"010101101100100",
"10101010101010",
"011010101110010",
"101010111010100",
"100110010101100",
"010011010100100",
"011010110001010",
"101000101010100",
"010010101100100",
"010101010011100",
"010101001100010",
"011100101010010",
"010010011010100",
"010110010100100",
"0110001101001000",
"010011011010100",
"010101000110010",
"101010101110100",
"011100101001010",
"010100110100100",
"011011011011010",
"010110010010100",
"010100110001010",
"010100101100100",
"101010100100010",
"001100101010100",
"0101010010010000",
"010010101101100",
"1100001010010100",
"010100100110100",
"010110011101010",
"011010101000110",
"010100110110100",
"010110110101100",
"010010110010100",
"011001010100100",
"010010100110100",
"011010010110100",
"0101100011001000",
"011011011010010",
"010011010110100",
"100110011011010",
"1101101101001000",
"100010101010100",
"011001001010100",
"011010101100100",
"100100110011010",
"010010100101100",
"0110100111011000",
"101101010100010",
"010010110101100",
"011011001010100",
"100110010011010",
"100110011010010",
"0101100010011000",
"101010010100010",
"101010101011000",
"011001010010100",
"100101100110010",
"1001101010001000",
"101011010100010",
"110101010100100",
"010110010110100",
"011010110010100",
"011010101101100",
"010101001100100",
"011100110101010",
"1011100101001000",
"011011010110110",
"010110110110010",
"0100110001101000",
"101000101010010",
"010110110010010",
"011001011010100",
"010110100101100",
"0010110011001000",
"011001010110100",
"011010011010100",
"1011001010110000",
"011010100110100",
"010011001010100",
"010101001001100",
"100101001100110",
"010010110010010",
"1000101101101000",
"010100110010100",
"110101010010100",
"011000110101010",
"100101010100010",
"101000101011010",
"010010101001100",
"110101001010100",
"011010010101100",
"0011001011001000",
"0101011011010000",
"010110011010100",
"0010101111010100",
"010100101001100",
"1001010110001000",
"010101001101100",
"010101100110100",
"110100101010100",
"100101010001010",
"011001010010010",
"0100011001110100",
"010011010101100",
"100110011001010",
"010110101001100",
"011011001001010",
"100010101010010",
"010101101001100",
"010100110101100",
"100101010111010",
"101010100100100",
"0101001000010100",
"011001101010100",
"0101000010010100",
"0101101011010000",
"100010101001010",
"010110010101100",
"1010101100110000",
"010101100101100",
"0110101001010000",
"100010101101010",
"1010110110111000",
"100010101011010",
"1010010111011000",
"0110101101010000",
"101101010100100",
"0101000010100100",
"1101011011001000",
"011010101001100",
"0101101111010100",
"101101101010100",
"100010110101010",
"010100110010010",
"101010010100100",
"010100100110010",
"1100100101001000",
"101011010100100",
"011010010011010",
"101010010010100",
"0101010001001000",
"101001010100100",
"1000100101011000",
"010101010101000",
"0011001001011000",
"1000101001101000",
"011001011010010",
"101010110100100",
"100010101010110",
"011010011010010",
"1000110110101000",
"101010101100010",
"011010010110010",
"101101010010100",
"101101011010100",
"101010110110100",
"1001110101101000",
"010011010110010",
"011011001010110",
"101010101110010",
"1001010001101000",
"0101100101010000",
"1000101011011000",
"1101001101001000",
"101001010010100",
"101101001010100",
"101010111001010",
"100101010100100",
"010110011010010",
"101010001101010",
"010110100110010",
"101011010010100",
"0100100010101000",
"011001101101010",
"101011010110100",
"100100101010100",
"011010010100110",
"1100101101001000",
"1010010010111000",
"010110010110010",
"011010110010110",
"1010111001101000",
"1010100111001000",
"101001011010100",
"1101100101101000",
"101001010110100",
"101010010010010",
"011001001101010",
"1001000101011100",
"101010010110100",
"100111010101010",
"0110101010001000",
"0101110101001000",
"100101010010100",
"100101001010100",
"011001010110010",
"0101110110101000",
"1101011011000100",
"0100101000101000",
"011010110011010",
"011001101001010",
"100101011010100",
"101101010010010",
"0001101010101000",
"011010011001010",
"011001010011010",
"101010101100100",
"100101101010100",
"1011011011100010",
"011001011001010",
"100101010110100",
"100011010101010",
"1010011100101000",
"101001010010010",
"101001001010010",
"0101011010110000",
"0101001010110000",
"0110110011000100",
"1000101100010100",
"1001011010111000",
"0101000111001100",
"101011010010010",
"101100101010100",
"0101010010110000",
"011010101100110",
"010110011001010",
"1000111011010100",
"101010101101100",
"101010110010100",
"011001010100110",
"101011001010100",
"100100100101010",
"1100101011001000",
"101101001010010",
"101010011010100",
"101101010101100",
"101001101010100",
"1010110001011000",
"0110011011100100",
"1101001011000100",
"0100101011101000",
"0101110100101000",
"101010100110100",
"100101010010010",
"101010110101100",
"101011010101100",
"100100101010010",
"0101011101000100",
"0110101010110000",
"101010010101100",
"1101011001101000",
"100101001001010",
"101001010101100",
"010101010100010",
"1010100100111000",
"101010100101100",
"0110001100100100",
"0011010111001100",
"100110101010100",
"0100110011011000",
"1001010001110100",
"0101010100110000",
"1011010100111000",
"100101001010010",
"0010010010101000",
"100100101011010",
"1100110101101000",
"100101101101010",
"1100101100101000",
"010101010001010",
"100100101101010",
"010101000101010",
"1000011011001010",
"010101110101010",
"0110010011101100",
"1010010100111000",
"0110110011100100",
"1101000110110100",
"1100101001101000",
"100101010101100",
"1101011010011000",
"100101101010010",
"100101011010010",
"101010110010010",
"1011010101010000",
"1011010011001000",
"101010110110010",
"001010101010100",
"1010011011001000",
"1010101001010000",
"0010010101000100",
"100100101010110",
"1010011001000100",
"101011001001010",
"100101001011010",
"101100101010010",
"1010100101010000",
"1101011001011000",
"1011001011001000",
"1010101101010000",
"101010101001100",
"101011001010010",
"101001001101010",
"101011010110010",
"0110001101101100",
"1011011001101000",
"1001100101001000",
"0010010110101000",
"1101101100100100",
"0101001001001000",
"1100110010101000",
"101001101010010",
"0010010101101000",
"100101001010110",
"101001010110010",
"101010011010010",
"1010101011010000",
"101010010110010",
"1001010011001000",
"0110011001011000",
"0010101101101000",
"011101010101010",
"1001001011000100",
"100110110101010",
"101001010011010",
"0100100101001000",
"1001101011001000",
"1011001101000100",
"0010100010100100",
"101001101001010",
"101001011001010",
"100100110101010",
"1100010101100100",
"100110101010010",
"1001011011100100",
"1101010110011000",
"1001010001100010",
"1100100111010100",
"0101001001000100",
"0100100100101000",
"1010011011101100",
"100101010110010",
"010101010100100",
"100110101101010",
"1001001110110100",
"100110101001010",
"1010110011001000",
"0101010001011000",
"0110101010111100",
"100101001101010",
"100110101011010",
"100101011001010",
"1011110101010100",
"0010110101101000",
"100110100101010",
"100101010011010",
"0101101001001000",
"0101010110111000",
"1100101110010100",
"100101100101010",
"1100101010011000",
"0101101101001000",
"0010101110100100",
"010010101010100",
"1011010011011000",
"101010100110010",
"0100100101000100",
"0011010101001000",
"1010101010001000",
"0010011010101000",
"1011001100101000",
"010101010010100",
"0100100100010100",
"1010111101010100",
"010100101010100",
"010101001010100",
"0100010100100100",
"010101101010100",
"010101011010100",
"100101010100110",
"101001100101010",
"010110101010100",
"0100101010111000",
"1001011001101000",
"0101101101101000",
"1010000101010100",
"1001101101011000",
"0111010101011000",
"1001101001101000",
"010101010110100",
"0101011010111000",
"1011001000110100",
"0011011010101000",
"0010101100101000",
"1001101011101100",
"0010100110101000",
"1100011010110100",
"0010110100010100",
"0101011101110010",
"0110110110101000",
"1011100100110100",
"1010110110011000",
"0111010110100010",
"0010111010110100",
"0100100101101000"
};
int phi(int x) {
int ans = x;
for (int i = 2; i * i <= x; ++i) if (x % i == 0) {
ans -= ans / i;
while (x % i == 0) x /= i;
}
if (x > 1) ans -= ans / x;
return ans;
}
int main () {
ios::sync_with_stdio(false);
cin.tie(0);
/*
for (int i = 1; i <= 2000; ++i) ans[i] = "-1";
for (int n = 1; n <= 16; ++n) {
for (int s = 0; s < 1 << n; ++s) {
string t;
for (int j = 0; j < n; ++j) {
if (s & (1 << j)) t.pb('1');
else t.pb('0');
}
vector <int> dp(n, 0);
dp[0] = 1;
for (int i = 1; i < n; ++i) {
int j;
for (j = i - 1; j >= 0; --j) {
if (t[i] == t[j]) break;
}
if (j == -1) dp[i]++, j++;
while (j < i) dp[i] += dp[j++];
}
int sum = accumulate(all(dp), 0);
if (sum <= 2000 && ans[sum] == "-1") ans[sum] = t;
}
}
cout << "{ ";
for (int i = 1; i <= 2000; ++i) {
cout << "\"" << ans[i] << "\",\n";
}
cout << "}\n";
*/
int t;
cin >> t;
while (t--) {
int x;
cin >> x;
string s = ans[x];
cout << phi(x + 2) << endl;
for (int i = 0; i < s.length(); ++i) cout << s[i] << ' ';
cout << endl;
}
}
Compilation message
binary.cpp: In function 'int main()':
binary.cpp:2071:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
2071 | for (int i = 0; i < s.length(); ++i) cout << s[i] << ' ';
| ~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
448 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
588 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
588 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
