Vova again tries to play some computer card game.
The rules of deck creation in this game are simple. Vova is given an existing deck of n cards and a magic number k. The order of the cards in the deck is fixed. Each card has a number written on it; number ai is written on the i-th card in the deck.
After receiving the deck and the magic number, Vova removes x (possibly x=0) cards from the top of the deck, y (possibly y=0) cards from the bottom of the deck, and the rest of the deck is his new deck (Vova has to leave at least one card in the deck after removing cards). So Vova's new deck actually contains cards x+1, x+2, ... n-y-1, n-y from the original deck.
Vova's new deck is considered valid iff the product of all numbers written on the cards in his new deck is divisible by k. So Vova received a deck (possibly not a valid one) and a number k, and now he wonders, how many ways are there to choose x and y so the deck he will get after removing x cards from the top and y cards from the bottom is valid?
Output
Print the number of ways to choose
x and
y so the resulting deck is
valid.
Note
In the first example the possible values of
x and
y are:
-
x=0,y=0;
-
x=1,y=0;
-
x=2,y=0;
-
x=0,y=1.
沃瓦再次尝试玩电脑纸牌游戏。
这个游戏中的牌组创建规则很简单。Vova被赋予一个现有的n张牌组和一个魔术数字k。牌组中的牌的顺序是固定的。每张卡片上都有一个数字；数字ai写在卡片组的第i张卡片上。
在收到牌组和魔法数字后，Vova从牌组顶部移除x（可能x=0）张牌，从牌组底部移除y（可能y=0）张卡，其余的牌组是他的新牌组（Vova在移除牌后必须在牌组中至少留下一张牌）。因此，Vova的新牌组实际上包含卡片x+1、x+2。。。n-y-1、n-y。
Vova的新牌组被认为是有效的，前提是他新牌组中写在牌上的所有数字的乘积都可以被k整除。因此Vova收到了一个牌组（可能不是有效的）和一个数字k，现在他想知道，有多少种方法可以选择x和y，这样他在从顶部移除x张牌和从底部移除y张牌后得到的牌组是有效的？