{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_epigraph\"\u003eThe Queen turned crimson with fury, and \u0026lt;…\u0026gt; screamed “Off with her head! Off—”\u003c/div\u003e\u003c/div\u003e\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eAfter talking to the Queen of Hearts, Alice understood one important thing:\r\none inappropriate word can make you beheaded.\r\nSo, Alice started to cipher her dialogues with her new friend Bandersnatch.\u003c/div\u003e\u003c/div\u003e\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eRecently she happened to invent a cipher which is easy in use, yet secure.\r\nAlice uses a sequence of integers \u003ci\u003ex\u003c/i\u003e\u003csub\u003e1\u003c/sub\u003e, …, \u003ci\u003ex\u003c/i\u003e\u003csub\u003e\u003ci\u003en\u003c/i\u003e\u003c/sub\u003e \u003cnobr\u003e(0 ≤ \u003ci\u003ex\u003c/i\u003e\u003csub\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e ≤ \u003ci\u003ea\u003c/i\u003e − 1)\u003c/nobr\u003e as a key; here, \u003ci\u003ea\u003c/i\u003e is the size of the alphabet.\r\nInstead of sending Bandersnatch a message \u003ci\u003es\u003c/i\u003e \u003d \u003ci\u003es\u003c/i\u003e\u003csub\u003e1\u003c/sub\u003e\u003ci\u003es\u003c/i\u003e\u003csub\u003e2\u003c/sub\u003e…\u003ci\u003es\u003c/i\u003e\u003csub\u003e\u003ci\u003er\u003c/i\u003e\u003c/sub\u003e,\r\nshe sends a message \u003ci\u003et\u003c/i\u003e \u003d \u003ci\u003et\u003c/i\u003e\u003csub\u003e1\u003c/sub\u003e\u003ci\u003et\u003c/i\u003e\u003csub\u003e2\u003c/sub\u003e…\u003ci\u003et\u003c/i\u003e\u003csub\u003e\u003ci\u003er\u003c/i\u003e\u003c/sub\u003e.\r\nHere, the alphabetic number of letter \u003ci\u003et\u003c/i\u003e\u003csub\u003e1\u003c/sub\u003e is the alphabetic number of\r\nletter \u003ci\u003es\u003c/i\u003e\u003csub\u003e1\u003c/sub\u003e plus the integer \u003ci\u003ex\u003c/i\u003e\u003csub\u003e1\u003c/sub\u003e, the number of \u003ci\u003et\u003c/i\u003e\u003csub\u003e2\u003c/sub\u003e is the number of\r\n\u003ci\u003es\u003c/i\u003e\u003csub\u003e2\u003c/sub\u003e plus the integer \u003ci\u003ex\u003c/i\u003e\u003csub\u003e2\u003c/sub\u003e, and so on; naturally, the next after the\r\nlast letter of the alphabet is the first one.\r\nAfter pronouncing the first \u003ci\u003en\u003c/i\u003e letters of her message, Alice uses\r\nher sequence from the beginning by using \u003ci\u003ex\u003c/i\u003e\u003csub\u003e1\u003c/sub\u003e, then \u003ci\u003ex\u003c/i\u003e\u003csub\u003e2\u003c/sub\u003e, and so on\r\n(for example, the number of \u003ci\u003et\u003c/i\u003e\u003csub\u003e\u003ci\u003en\u003c/i\u003e + 1\u003c/sub\u003e\r\nis the number of \u003ci\u003es\u003c/i\u003e\u003csub\u003e\u003ci\u003en\u003c/i\u003e + 1\u003c/sub\u003e plus \u003ci\u003ex\u003c/i\u003e\u003csub\u003e1\u003c/sub\u003e).\u003c/div\u003e\u003c/div\u003e\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eAlice wants to know the number of different keys for her cipher.\r\nThe keys that can be obtained from each other by a cyclic shift\r\n(e.\u0026nbsp;g., [0, 1, 2, 0] and [2, 0, 0, 1]) are considered the same.\r\nMoreover, Alice is afraid of eavesdropping, so she doesn\u0027t want to use\r\nsequences with period less than \u003ci\u003en\u003c/i\u003e\r\n(these are the sequences of length \u003ci\u003en\u003c/i\u003e which can be represented\r\nas shorter sequences repeated some integer number of times, like [0, 1, 0, 1]).\u003c/div\u003e\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eThe only line of input contains integers \u003ci\u003ea\u003c/i\u003e and \u003ci\u003en\u003c/i\u003e\r\n(1 ≤ \u003ci\u003ea\u003c/i\u003e ≤ 26; 1 ≤ \u003ci\u003en\u003c/i\u003e ≤ 10\u0026nbsp;000).\u003c/div\u003e\u003c/div\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eOutput the number of different keys for Alice\u0027s cipher.\u003c/div\u003e\u003c/div\u003e"}},{"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 4\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e18\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003cbr\u003e\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\u003e10 2\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e45\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}