Your relation in this case is (Ai XOR Bi) = 1 for some bit position i for less than 2. Basically this is a combinatoric argument where you can have:
0 difference (same numbers)
1 difference (8 possible differences)
2 difference (8C2 possible differences or 28 differences).
This means that for every number you have 1 + 8 + 28 or 37 possible numbers for each input that are "similar".
Can you take it from there?