BALTIC-WAY 1996 Problem 8

Consider the sequence

$$\begin{aligned} x_{1} & =19, \\ x_{2} & =95, \\ x_{n+2} & =\operatorname{lcm}\left(x_{n+1}, x_{n}\right)+x_{n}, \end{aligned}$$

for $n>1$, where $\operatorname{lcm}(a, b)$ means the least common multiple of $a$ and $b$. Find the greatest common divisor of $x_{1995}$ and $x_{1996}$.