Problem Description
You are given two 10-based integers b and x, and you are required to determine the following proposition is true or false:
For arbitrary b-based positive integer (y=overline{c_1c_2c_3...c_n})((c_i)is the i-th dight from left of y), define (f(y)=Sigma^n_{i=1}c_i), if (f(f(...f(y)...))) can be divided by x, then y can be divided by x, otherwise y can't be divided by x.
Input
The first line contains a 10-based integer t (1≤t≤(10^5)) — the number of test cases.
For each test case, there is a single line containing two 10-based integers b and x (2≤b,x≤(10^{18})).
Output
For each test case, if the proposition is true, print "T", otherwise print "F" (without quotes).
Sample Input
1
10 3
Sample Output
T
这道题的题面翻译一下，就是在什么情况下，对于b进制数x以及任意b进制数y，y的各位数字的和能被x整除可以推出y能被x整除；y的各位数字的和不能被x整除可以推出y不能被x整除。
题解直接放了结论出来：(bequiv1(mod x))。但这个是怎么来的呢？不妨把y这个数写出来：(y=c_1b^{n-1}+c_2b^{n-2}+...+c_nb^0)，会发现其实这是一个自变量为b的多项式的值。由同余的性质：若(aequiv b(mod m))，则(f(a)equiv f(b)(mod m))，其中(f(x))为整系数的一元多项式。因此如果令上式中a为1，b为题目中的b，那么可以由(bequiv 1(mod x))推出(y=c_1b^{n-1}+c_2b^{n-2}+...+c_nb^0equiv c_1+c_2+...+c_n(mod x))，而(c_1+c_2+...+c_n)就是翻译过来的题面里的y的各位数字的和。
上面只是大体思路，具体证明见官方题解：
原命题等价于：对于任意的 (b) 进制正整数 (y = overline{c_1 c_2 cdots c_n})，如果 (c_1 + c_2 + cdots + c_n equiv 0 pmod{x})，那么 (y equiv 0 pmod{x})，否则 (y otequiv 0 pmod{x})。
上述命题成立当且仅当 (b equiv 1 pmod{x})。
证明：
- 当 (b equiv 1 pmod{x}) 时，有 (y equiv c_1 b^{n-1} + c_2 b^{n-2} + cdots + c_n b^0 equiv c_1 + c_2 + cdots + c_n pmod{x})，于是上述命题成立。
- 当 (b
otequiv 1 pmod{x}) 时，假设上述命题成立，有：
- 若 (x leq b)，令 (y = 1 cdot b^1 + (x-1) b^0)，则应有 (y equiv b + x - 1 equiv 0 pmod{x})，即 (b equiv 1 pmod{x})，但此时 (b otequiv 1 pmod{x})，出现矛盾，于是上述命题不成立。
- 若 (x > b)，令 (y = x = overline{c_1 c_2 cdots c_n})，显然 (c_1 + c_2 + cdots + c_n otequiv 0 pmod{x})，于是 (y otequiv 0 pmod{x})，但 (y equiv 0 pmod{x})，出现矛盾，于是上述命题不成立。
综上，上述命题成立当且仅当 (b equiv 1 pmod{x})。