Under construction

Still being built. Things may change

Barbara Bennett's Wild Numbers

Interview

Time limit1sMemory limit128 MB

Summary
Given a wild number W with digit and ? positions and a same-length number X, count the length-n digit strings matching W that are strictly greater than X.
Level

Medium4 of 10

Topics
Combinatorics, Math, Implementation, Brute force
Solved
No attempts yet

Problem

A wild number is a string made of digits and question marks, such as 36?1?8. A number XX matches a wild number WW if they have the same length and every non-question-mark character of WW equals the character in the same position of XX (a question mark may be replaced by any single digit). For example, 365198 matches the wild number 36?1?8, but 360199, 361028, and 36128 do not. Given a wild number WW and a number XX of the same length nn, count how many length-nn digit strings match WW and are strictly greater than XX when the two are compared as numbers of the same length. Leading zeros are allowed.

Input

The input contains several test cases. Each test case consists of two lines of equal length: the first line holds a wild number WW, and the second line holds a number XX. Each line has length between 11 and 1010. The input ends with a line containing a single # character.

Output

For each test case, print on its own line the number of length-nn numbers that match WW and are greater than XX, where nn is the common length of WW and XX.

Examples2

  1. Example 1

    Input
    36?1?8
    236428
    8?3
    910
    ?
    5
    #
    
    Expected output
    100
    0
    4
    
  2. Example 2

    Input
    5
    4
    #
    
    Expected output
    1