{"trustable":true,"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":"\u003cp\u003eAfter a wonderful evening in the restaurant the time to go home came. Leha as a true gentlemen suggested Noora to give her a lift. Certainly the girl agreed with pleasure. Suddenly one problem appeared: Leha cannot find his car on a huge parking near the restaurant. So he decided to turn to the watchman for help.\u003c/p\u003e\u003cp\u003eFormally the parking can be represented as a matrix \u003cspan class\u003d\"tex-span\"\u003e10\u003csup class\u003d\"upper-index\"\u003e9\u003c/sup\u003e × 10\u003csup class\u003d\"upper-index\"\u003e9\u003c/sup\u003e\u003c/span\u003e. There is exactly one car in every cell of the matrix. All cars have their own machine numbers represented as a positive integer. Let\u0027s index the columns of the matrix by integers from \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e to \u003cspan class\u003d\"tex-span\"\u003e10\u003csup class\u003d\"upper-index\"\u003e9\u003c/sup\u003e\u003c/span\u003e from left to right and the rows by integers from \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e to \u003cspan class\u003d\"tex-span\"\u003e10\u003csup class\u003d\"upper-index\"\u003e9\u003c/sup\u003e\u003c/span\u003e from top to bottom. By coincidence it turned out, that for every cell \u003cspan class\u003d\"tex-span\"\u003e(\u003ci\u003ex\u003c/i\u003e, \u003ci\u003ey\u003c/i\u003e)\u003c/span\u003e the number of the car, which stands in this cell, is equal to the minimum positive integer, which can\u0027t be found in the cells \u003cspan class\u003d\"tex-span\"\u003e(\u003ci\u003ei\u003c/i\u003e, \u003ci\u003ey\u003c/i\u003e)\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e(\u003ci\u003ex\u003c/i\u003e, \u003ci\u003ej\u003c/i\u003e)\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003ei\u003c/i\u003e \u0026lt; \u003ci\u003ex\u003c/i\u003e, 1 ≤ \u003ci\u003ej\u003c/i\u003e \u0026lt; \u003ci\u003ey\u003c/i\u003e\u003c/span\u003e.\u003c/p\u003e\u003ccenter\u003e \u003cimg class\u003d\"tex-graphics\" src\u003d\"CDN_BASE_URL/a7650d5c90b51d5f251e96dc96c441da?v\u003d1715333573\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e \u003cspan class\u003d\"tex-font-size-small\"\u003eThe upper left fragment \u003cspan class\u003d\"tex-span\"\u003e5 × 5\u003c/span\u003e of the parking\u003c/span\u003e \u003c/center\u003e\u003cp\u003eLeha wants to ask the watchman \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eq\u003c/i\u003e\u003c/span\u003e requests, which can help him to find his car. Every request is represented as five integers \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ex\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e1\u003c/sub\u003e, \u003ci\u003ey\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e1\u003c/sub\u003e, \u003ci\u003ex\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e2\u003c/sub\u003e, \u003ci\u003ey\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e2\u003c/sub\u003e, \u003ci\u003ek\u003c/i\u003e\u003c/span\u003e. The watchman have to consider all cells \u003cspan class\u003d\"tex-span\"\u003e(\u003ci\u003ex\u003c/i\u003e, \u003ci\u003ey\u003c/i\u003e)\u003c/span\u003e of the matrix, such that \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ex\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e1\u003c/sub\u003e ≤ \u003ci\u003ex\u003c/i\u003e ≤ \u003ci\u003ex\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e2\u003c/sub\u003e\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ey\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e1\u003c/sub\u003e ≤ \u003ci\u003ey\u003c/i\u003e ≤ \u003ci\u003ey\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e2\u003c/sub\u003e\u003c/span\u003e, and if the number of the car in cell \u003cspan class\u003d\"tex-span\"\u003e(\u003ci\u003ex\u003c/i\u003e, \u003ci\u003ey\u003c/i\u003e)\u003c/span\u003e does not exceed \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ek\u003c/i\u003e\u003c/span\u003e, increase the answer to the request by the number of the car in cell \u003cspan class\u003d\"tex-span\"\u003e(\u003ci\u003ex\u003c/i\u003e, \u003ci\u003ey\u003c/i\u003e)\u003c/span\u003e. For each request Leha asks the watchman to tell him the resulting sum. Due to the fact that the sum can turn out to be quite large, hacker asks to calculate it modulo \u003cspan class\u003d\"tex-span\"\u003e10\u003csup class\u003d\"upper-index\"\u003e9\u003c/sup\u003e + 7\u003c/span\u003e.\u003c/p\u003e\u003cp\u003eHowever the requests seem to be impracticable for the watchman. Help the watchman to answer all Leha\u0027s requests.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line contains one integer \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eq\u003c/i\u003e\u003c/span\u003e \u003cspan class\u003d\"tex-span\"\u003e(1 ≤ \u003ci\u003eq\u003c/i\u003e ≤ 10\u003csup class\u003d\"upper-index\"\u003e4\u003c/sup\u003e)\u003c/span\u003e\u0026nbsp;— the number of Leha\u0027s requests.\u003c/p\u003e\u003cp\u003eThe next \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eq\u003c/i\u003e\u003c/span\u003e lines contain five integers \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ex\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e1\u003c/sub\u003e, \u003ci\u003ey\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e1\u003c/sub\u003e, \u003ci\u003ex\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e2\u003c/sub\u003e, \u003ci\u003ey\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e2\u003c/sub\u003e, \u003ci\u003ek\u003c/i\u003e\u003c/span\u003e \u003cspan class\u003d\"tex-span\"\u003e(1 ≤ \u003ci\u003ex\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e1\u003c/sub\u003e ≤ \u003ci\u003ex\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e2\u003c/sub\u003e ≤ 10\u003csup class\u003d\"upper-index\"\u003e9\u003c/sup\u003e, 1 ≤ \u003ci\u003ey\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e1\u003c/sub\u003e ≤ \u003ci\u003ey\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e2\u003c/sub\u003e ≤ 10\u003csup class\u003d\"upper-index\"\u003e9\u003c/sup\u003e, 1 ≤ \u003ci\u003ek\u003c/i\u003e ≤ 2·10\u003csup class\u003d\"upper-index\"\u003e9\u003c/sup\u003e)\u003c/span\u003e\u0026nbsp;— parameters of Leha\u0027s requests.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003ePrint exactly \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eq\u003c/i\u003e\u003c/span\u003e lines\u0026nbsp;— in the first line print the answer to the first request, in the second\u0026nbsp;— the answer to the second request and so on.\u003c/p\u003e"}},{"title":"Examples","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\u003e4\n1 1 1 1 1\n3 2 5 4 5\n1 1 5 5 10000\n1 4 2 5 2\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1\n13\n93\n0\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Note","value":{"format":"HTML","content":"\u003cp\u003eLet\u0027s analyze all the requests. In each case the requested submatrix is highlighted in blue.\u003c/p\u003e\u003cp\u003eIn the first request \u003cspan class\u003d\"tex-span\"\u003e(\u003ci\u003ek\u003c/i\u003e \u003d 1)\u003c/span\u003e Leha asks only about the upper left parking cell. In this cell the car\u0027s number is \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e. Consequentally the answer is \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e.\u003c/p\u003e\u003cp\u003e\u003cimg class\u003d\"tex-graphics\" src\u003d\"CDN_BASE_URL/fc0547d5db1f60610acf80a3cc13d03c?v\u003d1715333573\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e\u003c/p\u003e\u003cp\u003eIn the second request \u003cspan class\u003d\"tex-span\"\u003e(\u003ci\u003ek\u003c/i\u003e \u003d 5)\u003c/span\u003e suitable numbers are \u003cspan class\u003d\"tex-span\"\u003e4, 1, 2, 3, 2, 1\u003c/span\u003e. Consequentally the answer is \u003cspan class\u003d\"tex-span\"\u003e4 + 1 + 2 + 3 + 2 + 1 \u003d 13\u003c/span\u003e.\u003c/p\u003e\u003cp\u003e\u003cimg class\u003d\"tex-graphics\" src\u003d\"CDN_BASE_URL/16944fc278b8c0ef89dae2fd5cb2a4c5?v\u003d1715333573\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e\u003c/p\u003e\u003cp\u003eIn the third request \u003cspan class\u003d\"tex-span\"\u003e(\u003ci\u003ek\u003c/i\u003e \u003d 10000)\u003c/span\u003e Leha asks about the upper left frament \u003cspan class\u003d\"tex-span\"\u003e5 × 5\u003c/span\u003e of the parking. Since \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ek\u003c/i\u003e\u003c/span\u003e is big enough, the answer is equal to \u003cspan class\u003d\"tex-span\"\u003e93\u003c/span\u003e.\u003c/p\u003e\u003cp\u003e\u003cimg class\u003d\"tex-graphics\" src\u003d\"CDN_BASE_URL/66e07730ce25f18f6f635da3cde56a18?v\u003d1715333573\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e\u003c/p\u003e\u003cp\u003eIn the last request \u003cspan class\u003d\"tex-span\"\u003e(\u003ci\u003ek\u003c/i\u003e \u003d 2)\u003c/span\u003e none of the cur\u0027s numbers are suitable, so the answer is \u003cspan class\u003d\"tex-span\"\u003e0\u003c/span\u003e.\u003c/p\u003e\u003cp\u003e\u003cimg class\u003d\"tex-graphics\" src\u003d\"CDN_BASE_URL/4b7f9506e0a3e46428b8095ee146f403?v\u003d1715333573\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e\u003c/p\u003e"}}]}