配点 :

問題文


頂点からなる木が与えられます。 番目の辺は頂点 と頂点 を繋いでいます。また、 番目の頂点には正の整数 が書かれています。

パス が次の条件を満たすとき、そのパスは Coprime Path であると定義します。

頂点の組 のうち、頂点 から頂点 への最短パス Coprime Path であるものの個数を求めてください。

ただし、 の最大公約数を表します。

制約


  • 与えられるグラフは木である
  • 入力は全て整数である

入力


入力は以下の形式で標準入力から与えられます。






出力


頂点の組 のうち、頂点 から頂点 への最短パス Coprime Path であるものの個数を出力してください。

サンプル 1


入力1
3
1 2 3
1 2
1 3
出力1
3

頂点の組 として次の 通りがあります。

  • のとき、
  • のとき、
  • のとき、

このうち、 となる頂点の組は つあります。よって、答えは です。

サンプル 2


入力2
5
6 2 3 4 1
1 2
1 3
1 4
4 5
出力2
6

頂点の組 として次の 通りがあります。

  • のとき、
  • のとき、
  • のとき、
  • のとき、
  • のとき、
  • のとき、
  • のとき、
  • のとき、
  • のとき、
  • のとき、

このうち、 となる頂点の組は つあります。よって、答えは です。

サンプル 3


入力3
10
3 1 4 1 5 9 2 6 5 3
1 2
1 3
1 8
3 4
3 5
5 6
5 7
8 9
8 10
出力3
42

提出


Go (1.14)