H - Range Multiplication Query [Divisors ver.]

配点： 点

長さ の非負整数列 があります．
はじめ， です．

この数列 に対して， 回の操作を行ってください．
回目の操作は以下です：

• を満たす任意の整数 について， を で置換する．

その後， を満たす任意の整数 について，以下のように定められる整数値 を求めてください：

• の正の約数の個数 ．

• 入力はすべて整数

各テストケースの入力は，それぞれ以下の形式で与えられる：

個の整数 を空白区切りで一行に出力せよ．

1
5 8
1 1 3
2 2 1
3 3 4
4 4 1
5 5 5
1 3 2
2 4 3
3 4 4

4 4 12 6 2

回目までの操作後， を満たします．
回目までの操作後， を満たします．
回目までの操作後， を満たします．
回目までの操作後， を満たします．

1
4 8
1 1 42
2 2 32
3 3 23
4 4 49
1 3 88
2 4 77
1 4 23
1 2 41

160 216 72 16

2
4 2
1 2 2
2 3 3
3 3
2 3 3
1 2 1
1 3 1

2 4 2 1
1 2 2