Find the largest prime number $p<1000$ for which there exists a complex number $z$ satisfying

the real and imaginary part of $z$ are both integers;
$|z|=\sqrt{p},$ and
there exists a triangle whose three side lengths are $p,$ the real part of $z^{3},$ and the imaginary part of $z^{3}.$
Assume that $z=a+bi$. Then,
\[z^3=(a^3-3ab^2)+(3a^2b-b^3)i\]Note that by the Triangle Inequality,
\[|(a^3-3ab^2)-(3a^2b-b^3)|b$ (as otherwise, consider $i^3\overline z=b+ai$). If $|a/b|\geq 4$, then
\[17b^2\geq a^2+b^2>|a+b||a^2+b^2-4ab|\geq |b-4b||16b^2-16b^2+b^2|=3b^3\]`Thus, this means $b\leq\frac{17}3$ or $b\leq 5$. Also note that the roots of $x^2-4x+1$ are $2\pm\sqrt 3$, so thus if $b\geq 6$,
\[2\sqrt 3b=(2(2-\sqrt 3)-4)bp=a^2+b^2\geq 12b^2+b^2=13b^2\]so $b^2(a+b)(a^2+b^2-4ab)\geq (4+18)(4^2+18^2-4\cdot 4\cdot 18)>1000\]absurd. Thus, the answer is $\boxed{349}$.