LCM массивуудыг тоолох

2s

512MB

2324

0%

Additional Problems I

Хоёр бүхэл тоо $n$ , $k$ өгөгдөв. Бүх $1 \le i < n$ -д $\operatorname{lcm}(a_i, a_{i+1}) = k$ байх эерэг бүхэл тоон $a_1, a_2,\dots, a_n$ массивуудын тоог тоол.

Эх сурвалж: cses.fi

Оролтын формат

Эхний мөрөнд тестүүдийн тоо болох $t$ бүхэл тоо байна.

Дараагийн $t$ мөр бүрт хоёр бүхэл тоо $n$ , $k$ : массивын урт ба lcm-ийн утга.

Гаралтын формат

$t$ бүхэл тоо хэвлэ: тест бүрийн хариулт, $10^9 + 7$ -д хуваасан үлдэгдэл.

Хязгаарлалт

$1 \le t \le 1000$
$2 \le n \le 10^9$
$1 \le k \le 10^9$

Жишээ

Оролт1

Гаралт1

11
64
602746233

0.1 / 64 KiB

Редактор уншиж байна...