Description

小 Sub 收到了一道方程作为生日礼物，如下所示：$a^x \equiv x^a \pmod {2^p}$。给定 $a$ 的值，请你帮小 Sub 统计有多少个 $x$（$1 \leq x \leq 2^p$）满足该方程。

Input Format

有多组测试数据。输入的第一行为整数 $T$（约 $1000$），表示测试用例的数量。对于每组测试数据：

每组测试数据仅一行，包含两个整数 $a$ 和 $p$（$1 \leq a \leq 10^9$，$1 \leq p \leq 30$）。

Output Format

对于每组测试数据，输出一行一个整数，表示满足条件的 $x$ 的个数。

2
6 12
8 16

1023
16383

Hint

由 ChatGPT 5 翻译