{"trustable":false,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\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 type\u003d\"text/javascript\" async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS_HTML-full\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cstyle type\u003d\u0027text/css\u0027\u003e .input, .output {border: 1px solid #888888;} .output {margin-bottom:1em;position:relative;top:-1px;} .output pre,.input pre {background-color:#EFEFEF;line-height:1.25em;margin:0;padding:0.25em;} .title {background-color:#FFFFFF;border-bottom: 1px solid #888888;font-family:arial;font-weight:bold;padding:0.25em;} \u003c/style\u003e \u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027]], displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027]]}\n });\n \u003c/script\u003e\n \u003cscript type\u003d\"text/javascript\" async\n src\u003d\"https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\"\u003e\n \u003c/script\u003e\n\u003cp\u003eUniversal Studios Theme Parks announced a new game named \u003cspan class\u003d\"tex-font-style-tt\"\u003eThe Crazy Jumper\u003c/span\u003e, that is targeted problem solving fans.\u003c/p\u003e\n\u003cp\u003eIn this game, there are \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e large boxes numbered from \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e to \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e from left to right, such that the \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003csup class\u003d\"upper-index\"\u003e\u003ci\u003eth\u003c/i\u003e\u003c/sup\u003e\u003c/span\u003e box \u003cspan class\u003d\"tex-span\"\u003e(1 \u0026lt; \u003ci\u003ei\u003c/i\u003e ≤ \u003ci\u003en\u003c/i\u003e)\u003c/span\u003e is located to the right of the \u003cspan class\u003d\"tex-span\"\u003e(\u003ci\u003ei\u003c/i\u003e - 1)\u003csup class\u003d\"upper-index\"\u003e\u003ci\u003eth\u003c/i\u003e\u003c/sup\u003e\u003c/span\u003e box. Each box has a color, such that \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ec\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e is the color of the \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003csup class\u003d\"upper-index\"\u003e\u003ci\u003eth\u003c/i\u003e\u003c/sup\u003e\u003c/span\u003e box. \u003c/p\u003e\n\u003cp\u003eThe goal of the game is to reach the \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003csup class\u003d\"upper-index\"\u003e\u003ci\u003eth\u003c/i\u003e\u003c/sup\u003e\u003c/span\u003e box starting from the \u003cspan class\u003d\"tex-span\"\u003e1\u003csup class\u003d\"upper-index\"\u003e\u003ci\u003est\u003c/i\u003e\u003c/sup\u003e\u003c/span\u003e box, by jumping between the boxes. The player can do one of the following jumps: \u003c/p\u003e\n\u003col\u003e \n \u003cli\u003e Jump one box to the right. \u003c/li\u003e\n \u003cli\u003e If the player stands at a box of color \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ex\u003c/i\u003e\u003c/span\u003e, he/she can jump to the closest box of color \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ex\u003c/i\u003e\u003c/span\u003e that is to the right of him, if such box exist. \u003c/li\u003e\n\u003c/ol\u003e\n\u003cp\u003eZiad will be the first one to play the game, but he is not sure whether the game is amusing or not, so he wants to finish it with the minimum number of jumps. Can you help Ziad by telling him what is the minimum number of required jumps to reach the \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003csup class\u003d\"upper-index\"\u003e\u003ci\u003eth\u003c/i\u003e\u003c/sup\u003e\u003c/span\u003e box stating from the \u003cspan class\u003d\"tex-span\"\u003e1\u003csup class\u003d\"upper-index\"\u003e\u003ci\u003est\u003c/i\u003e\u003c/sup\u003e\u003c/span\u003e box? \u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line contains an integer \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eT\u003c/i\u003e\u003c/span\u003e, where \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eT\u003c/i\u003e\u003c/span\u003e is the number of test cases.\u003c/p\u003e\n\u003cp\u003eThe first line of each test case contains an integer \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e \u003cspan class\u003d\"tex-span\"\u003e(1 ≤ \u003ci\u003en\u003c/i\u003e ≤ 2 × 10\u003csup class\u003d\"upper-index\"\u003e5\u003c/sup\u003e)\u003c/span\u003e, where \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e is the number of the boxes in the game.\u003c/p\u003e\n\u003cp\u003eThe second line of each test case contains \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e integers \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ec\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e1\u003c/sub\u003e, \u003ci\u003ec\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e2\u003c/sub\u003e, ..., \u003ci\u003ec\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e \u003cspan class\u003d\"tex-span\"\u003e(1 ≤ \u003ci\u003ec\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e ≤ 2 × 10\u003csup class\u003d\"upper-index\"\u003e5\u003c/sup\u003e)\u003c/span\u003e, where \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ec\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e is the color of the \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003csup class\u003d\"upper-index\"\u003e\u003ci\u003eth\u003c/i\u003e\u003c/sup\u003e\u003c/span\u003e box.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eFor each test case, print a single line containing the minimum number of required jumps to reach the \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003csup class\u003d\"upper-index\"\u003e\u003ci\u003eth\u003c/i\u003e\u003c/sup\u003e\u003c/span\u003e box starting from the \u003cspan class\u003d\"tex-span\"\u003e1\u003csup class\u003d\"upper-index\"\u003e\u003ci\u003est\u003c/i\u003e\u003c/sup\u003e\u003c/span\u003e box.\u003c/p\u003e"}},{"title":"Example","value":{"format":"HTML","content":"\u003cdiv class\u003d\"sample-test\"\u003e\n \u003cdiv class\u003d\"input\"\u003e\n \u003cdiv class\u003d\"title\"\u003e\n Input\n \u003c/div\u003e\n \u003cpre\u003e3\u003cbr\u003e6\u003cbr\u003e9 2 4 7 1 5\u003cbr\u003e5\u003cbr\u003e1 2 1 1 4\u003cbr\u003e6\u003cbr\u003e1 2 3 1 3 2\u003cbr\u003e\u003c/pre\u003e\n \u003c/div\u003e\n \u003cdiv class\u003d\"output\"\u003e\n \u003cdiv class\u003d\"title\"\u003e\n Output\n \u003c/div\u003e\n \u003cpre\u003e5\u003cbr\u003e3\u003cbr\u003e2\u003cbr\u003e\u003c/pre\u003e\n \u003c/div\u003e\n\u003c/div\u003e"}},{"title":"Note","value":{"format":"HTML","content":"\u003cp\u003eAs input/output can reach huge size it is recommended to use fast input/output methods: for example, prefer to use \u003cspan class\u003d\"tex-font-style-tt\"\u003escanf/printf\u003c/span\u003e instead of \u003cspan class\u003d\"tex-font-style-tt\"\u003ecin/cout\u003c/span\u003e in C++, prefer to use \u003cspan class\u003d\"tex-font-style-tt\"\u003eBufferedReader/PrintWriter\u003c/span\u003e instead of \u003cspan class\u003d\"tex-font-style-tt\"\u003eScanner/System.out\u003c/span\u003e in Java.\u003c/p\u003e"}}]}