$\boxed{1064}$
$$\text{For a positive integer } k, \text{ denote the maximum nonnegative integer } i \text{ such that } 2^i \text{ divides } k \text{ by } v_2(k). \text{ Note that } v_2(kl) = v_2(k) + v_2(l) \text{ holds for any positive integers } k \text{ and } l, \text{ and that } v_2\left(\frac{k}{2}\right) = v_2(k) - 1 \text{ holds for any positive even number } k.$$
Lemma 1. Let $s$ and $t$ be positive integers.
* If $v_2(s) \neq v_2(t)$, we have $v_2(s + t) = \min\{v_2(s), v_2(t)\}$.

* If $v_2(s) = v_2(t)$, we have $v_2(s+t) > v_2(s)$.
Proof. We can write $s = 2^{v_2(s)}x$, $t = 2^{v_2(t)}y$ for some odd integers $x, y$.
In the case of $v_2(s) < v_2(t)$, we have $s+t = 2^{v_2(s)}(x+2^{v_2(t)-v_2(s)}y)$. Since $2^{v_2(t)-v_2(s)}y$ is even, $x+2^{v_2(t)-v_2(s)}y$ is odd. Thus $v_2(s+t) = v_2(s) = \min\{v_2(s), v_2(t)\}$ holds.
In the case of $v_2(s) > v_2(t)$ the same argument shows that $v_2(s+t) = \min\{v_2(s), v_2(t)\}$.
In the case of $v_2(s) = v_2(t)$, we have $s+t = 2^{v_2(s)}x + 2^{v_2(s)}y = 2^{v_2(s)}(x+y)$. Since $x+y$ is even, we have $v_2(s+t) > v_2(s)$. ■

Lemma 2. If $s, t \in \mathbb{N}$ satisfy $v_2(s) = v_2(t) \ge 1$, we have:
$$\bullet \quad v_2\left(t + \frac{s}{2}\right) = v_2\left(\frac{s}{2}\right) = v_2(s) - 1,$$
$$\bullet \quad v_2\left(s + \frac{t}{2}\right) = v_2\left(\frac{t}{2}\right) = v_2(s) - 1.$$
Proof. Since $v_2\left(\frac{s}{2}\right) = v_2(s) - 1 < v_2(s) = v_2(t)$, we have $v_2\left(t + \frac{s}{2}\right) = \min\{v_2(t), v_2\left(\frac{s}{2}\right)\} = v_2\left(\frac{s}{2}\right)$ by Lemma 1. Thus we have $v_2\left(t + \frac{s}{2}\right) = v_2\left(\frac{s}{2}\right) = v_2(s) - 1$. Similarly $v_2\left(s + \frac{t}{2}\right) = v_2\left(\frac{t}{2}\right) = v_2(t) - 1 = v_2(s) - 1$ holds. ■

We will show that, if $a_1, a_2, \dots$ and $b_1, b_2, \dots$ satisfy the condition of the problem, $v_2(a_1) \ne v_2(b_1)$ holds.
Assume $v_2(a_1) = v_2(b_1)$. If $v_2(a_1) = v_2(b_1) = 0$, $a_2$ cannot be an integer. If $v_2(a_1) = v_2(b_1) = k \ge 1$, Lemma 2 shows inductively that $v_2(a_n) = v_2(b_n) = k - n + 1$ for $n \le k + 1$. However, when $n = k + 1$ we have $v_2(a_n) = v_2(b_n) = 0$, then $a_{n+1}$ cannot be an integer. This is a contradiction and we conclude that $v_2(a_1) \ne v_2(b_1)$.
Next we will show that, for any integers $1 \le s, t \le 40$ with $v_2(s) \ne v_2(t)$, there exists sequences $a_1, a_2, \dots$ and $b_1, b_2, \dots$ such that $a_1 = s$ and $b_1 = t$.
Lemma 3. If $s, t \in \mathbb{N}$ satisfy $v_2(s) \ne v_2(t)$, at least one of the following statements hold:
* $s$ is even and $v_2\left(t + \frac{s}{2}\right) \ne v_2\left(\frac{s}{2}\right)$ holds.
* $t$ is even and $v_2\left(s + \frac{t}{2}\right) \ne v_2\left(\frac{t}{2}\right)$ holds.
Proof. We will show that if $v_2(s) > v_2(t)$ the first condition holds. $s$ is even because $v_2(s) \ge 1$.
If $v_2(s) = v_2(t) + 1$, we have $v_2\left(\frac{s}{2}\right) = v_2(s) - 1 = v_2(t)$ and thus $v_2\left(t + \frac{s}{2}\right) > v_2\left(\frac{s}{2}\right)$ by Lemma 1. If $v_2(s) \ge v_2(t) + 2$, we have $v_2\left(\frac{s}{2}\right) = v_2(s) - 1 > v_2(t)$ and thus $v_2\left(t + \frac{s}{2}\right) = \min\{v_2(t), v_2\left(\frac{s}{2}\right)\} = v_2(t) < v_2\left(\frac{s}{2}\right)$ by Lemma 1.

Let $a_1 = s, b_1 = t$. Then for $n = 1, 2, \dots$ we can proceed inductively as follows:
Since $v_2(a_n) \neq v_2(b_n)$, Lemma 3 shows that at least one of $(x, y) = \left(\frac{a_n}{2}, b_n + \frac{a_n}{2}\right)$, $\left(a_n + \frac{b_n}{2}, \frac{b_n}{2}\right)$ is a pair such that $v_2(x) \neq v_2(y)$. We set $a_{n+1} = x, b_{n+1} = y$ for such $(x, y)$.
The resulting sequences $a_1, a_2, \dots$ and $b_1, b_2, \dots$ meet the condition of the problem. Therefore the answer is the number of pairs of integers $(s, t)$ with $1 \le s, t \le 40$ such that $v_2(s) \neq v_2(t)$.
Note that $v_2(n) \le 5$ for $1 \le n \le 40$ because $40 < 2^6$. For $k \in \{0, 1, \dots, 5\}$, the number $f(k)$ of integers $1 \le n \le 40$ such that $v_2(n) = k$ is $\lfloor \frac{40}{2^k} \rfloor - \lfloor \frac{40}{2^{k+1}} \rfloor$. Thus we can calculate
$$f(0) = 20, \quad f(1) = 10, \quad f(2) = 5, \quad f(3) = 3, \quad f(4) = 1, \quad f(5) = 1.$$
The number of pairs of integers $(s, t)$ with $1 \le s, t \le 40$ such that $v_2(s) = v_2(t)$ is $\sum_{k=0}^{5} f(k)^2 = 536$. Therefore, the answer is $40^2 - 536 = \mathbf{1064}$.