{"trustable":true,"prependHtml":"\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"panel_content\"\u003e\u003ci\u003eAcknowledgment: Special thanks to Codeforces Problem 1548B Integer Have Friends for providing the general statement for this problem.\u003c/i\u003e\u003cbr\u003e\u003cbr\u003eIndian mathematician Srinivasa Ramanujan once quoted the famous words of Indian mathematician Srinivasa Ramanujan(?) that \"every positive integer was one of his personal friends.\"\u003cbr\u003e\u003cbr\u003eIt turns out that positive integers can also be friends with each other! You are given an array $a$ of distinct positive integers.\u003cbr\u003e\u003cbr\u003eDefine a \u003cb\u003esubsequence\u003c/b\u003e $a_{c_1}, a_{c_2},\\dots,a_{c_k}$ where $k\\geq 1$ and $1\\leq c_1\u0026lt;c_2\u0026lt;\\dots\u0026lt;c_k\\leq n$ to be a friend group if and only if there exists an integer $m\\geq 2$ such that $a_{c_1}\\mod m\u003da_{c_2} \\mod m\u003d\\dots\u003da_{c_k} \\mod m$, where $x \\mod y$ denotes the remainder when $x$ is divided by $y$.\u003cbr\u003e\u003cbr\u003eYour friend gispzjz wants to know the size of the largest friend group in $a$. Can you help him?\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"The first line contains a number $T(1\\leq T\\leq 30)$, denoting the number of test cases.\u003cbr\u003e\u003cbr\u003eThe first line of each test case contains one integer $n(2\\leq n\\leq 2\\times 10^5)$, denoting the size of the array $a$.\u003cbr\u003e\u003cbr\u003eThen one line containing $n$ integers $a_1,a_2,\\dots,a_n(1\\leq a_i\\leq 4\\times 10^{12})$ follow, representing the contents of the array $a$. \u003cb\u003eIt is guaranteed that all the numbers in $a$ are distinct.\u003c/b\u003e\u003cbr\u003e \u003cbr\u003eIt is guaranteed that $\\sum n\\leq 10^6$ over all test cases."}},{"title":"Output","value":{"format":"HTML","content":"For each test case, output a line consisting of a single integer, denoting the size of the largest friend group in $a$."}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3\r\n3\r\n10 12 15\r\n4\r\n4 6 9 19\r\n6\r\n2 8 11 15 19 38\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2\r\n3\r\n4\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}