\(\max(X_1, X_2) \le \mathrm{lcm}(X_1, X_2) \le X_1X_2\) なので，\(\max(A_1, A_2) > A_3\) または \(A_1 + A_2 < A_3\) のときは明らかに存在しません． そうでないとき，非負整数 \(i_1, j_1, k_1, i_2, j_2, k_2\) を用いて \(X_1 = 2^{i_1} 3^{j_1} 5^{k_1}\), \(X_2 = 2^{i_2} 3^{j_2} 5^{k_2}\) と表せるような解が存在することを示します．

対称性から \(A_1 \le A_2\) を仮定してよいです． \(\ell = (A_1 - 1) + (A_2 - 1) - (A_3 - 1) = A_1 + A_2 - A_3 - 1\) とすると，\(A_1 \le A_2 \le A_3\) より \(\ell \le A_1 - 1 \le A_2 - 1\) が成り立ちます． 以下では，\(\mathrm{gcd}(X_1, X_2) = 10^\ell\) であるような解を構築します．

まず，\((i_1, j_1, k_1) = (A_1 - 1, 0, A_1 - 1)\) とします． このとき \(X_1 = 10^{A_1 - 1}\) は \(A_1\) 桁の整数であり，\(10^\ell\) の倍数になっています．

次に，\((i_2, j_2, k_2) = (\ell, j_2, \ell)\) とします． このとき \(X_2 = 3^{j_2} \cdot 10^\ell\) であり，\(\ell \le A_2 - 1\) なので，\(X_2\) がちょうど \(A_2\) 桁になるような非負整数 \(j_2\) が存在する（桁数は \(j_2\) に関して単調非減少であり，整数を \(3\) 倍したときに桁数が \(2\) 以上上がることは無い）ので，そのようなものを \(1\) つ選びます．

作り方から明らかに \(\mathrm{gcd}(X_1, X_2) = 10^\ell\) であり，

\[\mathrm{lcm}(X_1, X_2) = \frac{X_1X_2}{\mathrm{gcd}(X_1, X_2)} = \frac{3^{j_2} \cdot 10^{A_1 - 1 + \ell}}{10^\ell} = 3^{j_2} \cdot 10^{A_1 - 1}\]

です．ここで，\(X_2\) が \(A_2\) 桁になるように \(j_2\) を選んでいるので，\(\mathrm{lcm}(X_1, X_2)\) の桁数は \(A_2 + (A_1 - 1) - \ell = A_3\) となり，条件を満たします．

したがって，\(2^i 3^j 5^k\) の形の整数を列挙して桁数を調べておき，その中から所望の組合せを見つければよいです． 上の構成方法から \(i = k\) の場合に絞ってもよく，そのような正整数は \(10^{17}\) 未満の範囲に \(330\) 個しかないため，\(T \le 17^3 \approx 5000\) 個の入力に対して全探索したとしても制限時間に間に合います．