Мистер Х преподает теорию чисел в своем классе. Он обсуждает факторы
и перестановки в своем классе. Фактор положительного целого числа N является положительным
целое число, которое делит n точно (не оставляя остатка). Набор
факторы всегда включают 1 и N.
Мистер Х очень любит комбинаторику. Он попросил своих учеников выяснить все факторы числа Y и отсортировать их в порядке возрастания. Он просит их перечислить все
перестановки факторов. Затем они должны вычеркнуть все перестановки
где два соседних числа смежны в том же порядке в оригинале
список. Количество пересеченных (действительных) перестановок должно быть дано ему.
Иллюстрация:
Целое число
9
имеет
3
множителей
[1,3,9]
.
Перестановки этих факторов числа
9
are
[1,3,9],[1,9,3],[3,9,1],[3,1,9], [9,1,3],[9,3,1]
.
Из этих
6
перестановок нам необходимо вычеркнуть
[1,3,9]
(1 3 смежных в том же
порядок),
[3,9,1]
(3 9 в том же порядке) и
[9,1,3]
(1 3 в том же порядке)
Остальные (действительные) перестановки:
[1,9,3] ,[9,3,1],[3,1,9]
Отсюда количество действительных перестановок = 3, что является ответом
Input
1
10
Output
11
Explanation
T=1 (there is 1 test case)
N=10.
10 has 4 factors [1,2,5,10]. There are 24 permutations of these four factors.
The 11 valid permutations are [1,5,2,10],[1,10,5,2], [2,1,10,5],[2,10,1,5], [2,10,5,1],
[5,1,10,2], [5,2,1,10], [5,2,10,1], [10,1,5,2], [10,2,1,5], [10,5,2,1]. Hence the output
is 11