After talking to the Queen of Hearts, Alice understood one important thing: one inappropriate word can make you beheaded. So, Alice started to cipher her dialogues with her new friend Bandersnatch.

Recently she happened to invent a cipher which is easy in use, yet secure. Alice uses a sequence of integers x₁, …, x_n (0 ≤ x_i ≤ a − 1) as a key; here, a is the size of the alphabet. Instead of sending Bandersnatch a message s = s₁s₂…s_r, she sends a message t = t₁t₂…t_r. Here, the alphabetic number of letter t₁ is the alphabetic number of letter s₁ plus the integer x₁, the number of t₂ is the number of s₂ plus the integer x₂, and so on; naturally, the next after the last letter of the alphabet is the first one. After pronouncing the first n letters of her message, Alice uses her sequence from the beginning by using x₁, then x₂, and so on (for example, the number of t_{n + 1} is the number of s_{n + 1} plus x₁).

Alice wants to know the number of different keys for her cipher. The keys that can be obtained from each other by a cyclic shift (e. g., [0, 1, 2, 0] and [2, 0, 0, 1]) are considered the same. Moreover, Alice is afraid of eavesdropping, so she doesn't want to use sequences with period less than n (these are the sequences of length n which can be represented as shorter sequences repeated some integer number of times, like [0, 1, 0, 1]).

The only line of input contains integers a and n (1 ≤ a ≤ 26; 1 ≤ n ≤ 10 000).

Output the number of different keys for Alice's cipher.