{"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":"MD","content":"Có $n$ người sống ở $n$ thành phố khác nhau. Ban đầu, không có con đường nào nối hai thành phố bất kỳ với nhau (tức là không có cách nào để hai người bất kỳ tới thăm nhau cả). Chính phủ lên kế hoạch xây dựng các con đường trong $m$ ngày như sau:\n- Ngày đầu tiên, xây dựng xong các con đường nối hai cặp thành phố có ước chung lớn nhất là $m$;\n- Ngày thứ hai, xây dựng xong các con đường nối hai cặp thành phố có ước chung lớn nhất là $m-1$;\n $\\cdots$\n- Ngày thứ $m$, xây dựng xong các con đường nối hai cặp thành phố đồng nguyên tố.\n\nBạn cần trả lời $q$ truy vấn, mỗi truy vấn gồm hai số nguyên $A,B (1\\le A,B \\le n)$ yêu cầu bạn xác định xem sau ít nhất bao nhiêu ngày xây dựng thì hai người ở hai thành phố $A$ và $B$ có thể đến thăm nhau được."}},{"title":"Input","value":{"format":"MD","content":"- Dòng 1: ghi ba số nguyên $n,m,q (1 \\leq n, q \\leq 10^5, 1 \\leq m \\leq n)$;\n- Tiếp theo là $q$ dòng, mỗi dòng mô tả một truy vấn gồm hai số nguyên $A$ và $B$."}},{"title":"Output","value":{"format":"MD","content":"- Ghi trên $q$ dòng, mỗi dòng gồm một số nguyên là câu trả lời cho truy vấn tương ứng."}},{"title":"Examples","value":{"format":"MD","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\u003e10 3 1\n2 8\n\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\u003e2\n\u003c/pre\u003e\n \u003c/div\u003e\n\u003c/div\u003e"}}]}