One day, little $\Delta$ gave you a piece of paper with a very large number $n$ written on it. He wants you to factorize it into prime factors within one second. You take a closer look and realize that the binary representation of this number has up to $1500$ bits. You search online and find that even RSA-1024 has not been factored yet, so how could it be possible to factor this in one second?

However, you suddenly notice that he also wrote something on the back of the paper. You look again and see that it is $\varphi(n)$, which is the number of positive integers $\leq n$ that are coprime to $n$.

Now you seem to understand how to factor it. You open your computer, copy your ancestral high-precision integer arithmetic library, and wonder: can you tell little $\Delta$ the result in one second?

Input

A single line containing two binary integers $n$ and $\varphi(n)$.

Output

If $n$ can be represented as $n=\prod_{i=1}^T p_i$, where $p_i$ are prime numbers and $\forall 1\leq i < T, p_i\leq p_{i+1}$, then first output a line containing a decimal non-negative integer $T$. Following this, output $T$ lines, each containing a binary integer representing $p_i$. It can be proven that such a representation is unique.

Examples

Input 1

11111101 11011100

Output 1

2
1011
10111

Input 2

See the provided files.

Subtasks

For all data, $1\leq n< 2^{1500}$.

This problem uses bundled testing. The subtasks are as follows:

1. $n< 2^{32}$ (5 points)
2. $n< 2^{64}$ (15 points)
3. $n< 2^{300}$, $n=pq$, where $p, q$ are distinct prime numbers (10 points)
4. $n< 2^{300}$, $n=\prod_{i=1}^T p_i$, where $p_i$ are pairwise distinct prime numbers, and $p_i\equiv 3\pmod{4}$ (15 points)
5. $n< 2^{300}$, $n=\prod_{i=1}^T p_i$, where $p_i$ are pairwise distinct prime numbers (15 points)
6. $n< 2^{300}$ (25 points)
7. No special restrictions (15 points)

It is guaranteed that each subtask contains no more than 15 test cases, but all feasible dependencies between subtasks are set.

Implementation Details

We have provided the "ancestral high-precision integer arithmetic library" mentioned in the problem statement in the provided files. Please refer to the documentation included in the provided files for details.