Awkward Digits

Interview

Time limit1sMemory limit128 MB

Summary

Given a binary string and a ternary string that each differ from the true base-2 and base-3 forms of N in exactly one digit, find N.

Level: Medium5 of 10
Topics: Brute force, Math, Implementation, Hash map
Solved: No attempts yet

Problem

Bessie the cow is learning how to convert numbers between different bases, but she keeps making mistakes because she cannot easily hold a pen between her two front hooves.

Every time Bessie converts a number to a new base and writes down the result, she gets exactly one digit wrong. For example, when she converts the number 14 into base 2 (binary), the correct result is 1110, but she might instead write 0110 or 1111. She never accidentally adds or removes digits, so the number of digits she writes is always correct — she may even write a leading 0 if that is the digit she gets wrong.

You are given Bessie's two write-ups for the same number N: her base-2 conversion (with exactly one wrong digit) and her base-3 conversion (with exactly one wrong digit). Determine the correct original value of N in base 10.

N is at most one billion (1,000,000,000), and the answer is guaranteed to be unique.

Input

Line 1: Bessie's base-2 representation of N, with exactly one digit written incorrectly.
Line 2: Bessie's base-3 representation of N, with exactly one digit written incorrectly.

Output

Line 1: The correct value of N.

Sample Explanation

In the sample, Bessie's base-2 write-up is 1010 and her base-3 write-up is 212. The correct answer is N = 14: its true base-2 form is 1110 and its true base-3 form is 112, and each of Bessie's write-ups differs from the correct form in exactly one digit.

Examples3

Example 1
Input
```
1010
212
```
Expected output
```
14
```
Example 2
Input
```
0
0
```
Expected output
```
1
```
Example 3
Input
```
11
1
```
Expected output
```
2
```